Skip to content

Instantly share code, notes, and snippets.

@saran87
Created August 23, 2012 19:24
Show Gist options
  • Save saran87/3440598 to your computer and use it in GitHub Desktop.
Save saran87/3440598 to your computer and use it in GitHub Desktop.
candies - interview street problem
#include <iostream>
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<N; i++){
cin>>rating[i];
}
for ( int i = 0; i<N ; i++){
//Each student gets at least one candy
candies[i] = 1 ;
//Check boundary condition
if( i-1 >= 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<N ; i++){
total += candies[i];
}
//display the candies
cout<<total;
system("pause");
return 0;
}
@ibbyzj
Copy link

ibbyzj commented Sep 30, 2012

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

@agrawalh
Copy link

In worst case it is O(N^2) solution.

Is there a better solution for this problem ??

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment