Skip to content

Instantly share code, notes, and snippets.

@saran87 saran87/candies.cpp
Created Aug 23, 2012

Embed
What would you like to do?
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

This comment has been minimized.

Copy link

ibbyzj commented Sep 30, 2012

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

@agrawalh

This comment has been minimized.

Copy link

agrawalh commented Jan 21, 2013

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
You can’t perform that action at this time.