Instantly share code, notes, and snippets.

# saran87/candies.cpp Created Aug 23, 2012

candies - interview street problem
 #include using namespace std; int main() { int N; //Get Number of students cin>>N; //initialize rating and candidates array int *rating = new int[N]; int *candies = new int[N]; //get rating of each student for (int i=0; i>rating[i]; } for ( int i = 0; i= 0){ //Look for previous student rating and if it less than current student //assign the current student rating to the previous student rating plus one if( rating[i-1] < rating[i]){ candies[i] = candies[i-1]+1; } //Other wise if previous student rating is greater than current student //Imagine it as slope of mountain for example consider rating in decreasing order( 9 8 7 6 5 4) // so the number of candies has to increased for all previous students else { int j = i; while (j>0 && rating[j-1] > rating[j]) { //check is the current student already has max number of candidates //for example if students are arranged in below fashion // 123456 7 5432 //here 7 will have more candies if we go back from 2 it will result in 5/4 candies which violates the rule from the front candies[j-1] = max(candies[j-1],candies[j] + 1); j= j-1; } } } } //sum up all the candies of the students int total = 0; for ( int i = 0; i

### ibbyzj commented Sep 30, 2012

 nice :), helped me figure out a bug in my code.

### agrawalh commented Jan 21, 2013

 In worst case it is O(N^2) solution. Is there a better solution for this problem ??