# C, 19 lines of code, one pass, O(n), O(1) solution

• 'c' is number of candies, 'a' is length of ascending sequence, 'd' is length of descending sequence.

``````int candy( int* r, int n )
{
int c = 1, a = 1, d = 1;
for( int i = 1; i < n; ++i )
{
if( r[i] < r[i-1] )
{
++d;
continue;
}
c += d * (d - 1) / 2 + (d > a ? d - a : 0);
if( r[i] == r[i-1] )
a = 0, d = 1;
else if( d > 1 )
a = 1, d = 1;
c += ++a;
}
return c + d * (d - 1) / 2 + (d > a ? d - a : 0);
}
``````

and it is a concision of below code which is more easy to understand.

``````int candy( int* r, int n )
{
int c = 1, a = 1, d = 1;
for( int i = 1; i < n; ++i )
{
if( r[i] > r[i-1] ) // in a ascending sequence
{
if( d > 1 ) // a descending sequence ended here?
{
// add candies for the descending sequence but exclude the first child,
//  the formula is simplified from '((d - 1) + 1) * (d - 1) / 2'
c += d * (d - 1) / 2;
// adjust candies for the last child in previous ascending sequence if needed,
// note he is also the first child in the descending sequence
if( d > a )
c += d - a;
a = d = 1; // reset length of ascending & descending sequence
}
++a; // update length of ascending sequence
c += a; // add candies for current child
}
else if( r[i] == r[i-1] )
{
// same as the start of ascending sequence,
// add candies for the descending sequence if this end a descending sequence,
// note this will be '0' if 'd' is 1
c += d * (d - 1) / 2;
if( d > a )
c += d - a;
// add candy for current child, always '1'
// (poor child, he scores same as his neighbour but get less)
++c;
a = d = 1;  // reset length of ascending & descending sequence
}
else
{
++d; // update the length of descending sequence
}
}
c += d * (d - 1) / 2; // handle the last descending sequence
if( d > a )
c += d - a;
return c;
}``````

• can you explain your solution? i cant understand

• i've added my previous version with comment, the latest version is a concision of this version

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.