- Practice
- Algorithms
- Greedy
- Candies
- Discussions

# Candies

# Candies

gnawer + 22 comments I solved it, but I have no idea how to prove my solution is correct. First I go left to right and set "next" candy value to either "previous+1" or "1". This way I get the up trends. Then I go right to left and do the same, this way getting the down trends. Very simple O(2xN) solution, but doesn't look like it's the intended one.

amazinghacker + 1 comment did all the test cases pass?

gnawer + 2 comments Yes.

- K
knikitin + 0 comments [deleted] - MP
mansi1795 + 3 comments i did exactly the same,however it failed two test cases :(

- MK
kwiatek999 + 3 comments I had the same - I think you accumulate the result on an int that is overflowing, try long long

- JL
vvvincentvan + 0 comments I think the problem might be that it's not exactly up or down trends, when you go throuth the sequence from both side, and meet in the middle, you don't have to raise all the value in the left part or the right part. I think the best way is divide and conquer algorithm.

enricogiurin + 0 comments I had the same 2 tests failing. It was enough to save the sum in a long, rather than in a int.

animeshy2jj + 0 comments Using long worked for me.

nikunj_gupta447 + 4 comments try this test case:-

10

9 2 3 6 5 4 3 2 2 2vicky2922 + 3 comments [deleted]- GA
gauravagarwal271 + 0 comments how answer will be 20?

ranchoparikh + 0 comments [deleted]- RG
rav_gupta11 + 1 comment how it is 20?

- RG
rav_gupta11 + 2 comments In your solution '<' should be there instead of '<=', read first solved example.

vicky2922 + 0 comments [deleted]vicky2922 + 2 comments `for(int i = 1 ; i < n ;i++){ //forward track if(arr[i] > arr[i-1]){ dp[i] = dp[i] + dp[i-1]; } } for(int i = n-2 ; i >= 0 ; i--){ // back track if(arr[i] > arr[i+1] && dp[i] <= dp[i+1]){ dp[i] = dp[i+1] + 1; } } its 22 ..`

- PD
paul_dirac + 0 comments [deleted] - PK
khushlanipiyush + 0 comments I don't think it's a true dp as we are doing reinforcement in the dp array which is not done generally. I also had somewhat same solution but my array name was not dp as mentioned earlier.

- JT
thakkarjinal99 + 0 comments [deleted] - SR
smritirastogi33 + 0 comments 22?

- RP
rutulpatel2000 + 0 comments [deleted]

nikitac + 0 comments take the data type of result as long long int instead of int

- EY
ehapmgs + 0 comments [deleted] smallet + 1 comment Interesting. I implemented both - dynamic and this solution and found that performance is about the same, but it varies - in some cases dynamic solution is better, while in others your solution is.

- DG
deepak108 + 0 comments Can you please explain how you applied dynamic programming method.

ecastroborsani + 0 comments [deleted]raj_rajvir + 0 comments how many candies did you give to the first child??

cgira + 0 comments I have same solution working on given testcases but it doesn't work for hidden ones. I scored just 5 :-(

karananeja1996 + 1 comment can thi algo traverse 9,8,7,7,6,6,5,4,3,

i think no????

- G
gschoen + 3 comments Sure it does.

After the forward sweep, each child has 1 candy because each child has a rating equal to or less than that of its predecessor.

After the backward sweep, the 5th child has 1 candy and the 6th child has 4 candies (because the each have a rating of 6) while the 3rd child has 1 candy and the 4th child has 2 candies (because they each have a rating of 7).

So, the final rating:candies distribution is:

9:3 8:2 7:1 7:2 6:1 6:4 5:3 4:2 3:1 for a total of 19 candies.dimple97verma + 0 comments thanks alot !!ur this post helped me!!

dimple97verma + 0 comments [deleted]rahulrs097 + 1 comment How about : 9:2 5:1 8:2 7:1 7:2 6:1 6:3 4:2 3:1 -> 15 candies there may be a better solution

- JL
a20145582 + 0 comments their positions are fixed

- V
gvir_hr + 0 comments Please check out this blog http://stackandqueue.com/?p=108, it explains why standard solution actually works. Trick is to understand why local minimas will get 1 candy and then you can get candies for other students

lizzael_v_c + 0 comments I did the same. Is O(N), so is optimal.

- GD
maheshud + 2 comments This is excellent solution. Note that two testcases may fail due to size of the resulting sum: Int vs Long

Rumperthumskin + 0 comments Ugh... yes got tripped up by int vs long (Java solution). Thanks!

shri_ranjani + 0 comments Thank you so much!

- AS
Akshita_Sood + 0 comments [deleted] - AS
Akshita_Sood + 0 comments But this gives me answer of second test case =20. Please explain. How do you explain the overlapping answers?

zirho6 + 0 comments I solved it in the same manner. O(2xN) is O(N). This does not need DP at all.

ayushr2 + 0 comments here is an explanation: We basically have to find sequences of numbers which are always increasing and those which are decreasing. initialise a count array of length n with all 1. then whenever u see an increasing pattern, set the bigger number count = smaller number count + 1 while traversing the array forward. then traverse the array backwards and check for the same increasing pattern (which would be decreasing since we are traversing backward). but only do the bigger number count = smaller number count + 1 when (bigger number count <= smaller number count). this is because we might already have set the value to something bigger before while traversing forward. here is an example, array : 2 4 5 6 7 8 9 5 4 count : 1 2 3 4 5 6 7 2 1 count array can look like a mountain. increase then decrease the peak of the mountain (9 here) is determined by which slope is longer, left or right. that is why u have that check while traversing backards. try manually doing this and u will see why: array : 2 9 8 6 4 3 2 1 count : 1 7 6 5 4 3 2 1

dhruvkumarbansal + 1 comment My solution is simmilar to yours. Logic behind this is that if you make a graph between marking and index of child then local minima will always have 1(min) candy. Then next on both sides of local minima will have 1(min) + 1 candy and so on. This approach can be easily implemented by the method you mentioned above.

candies[0] = 1; for(int i = 1; i < markings.length; i++) { candies[i] = (markings[i] > markings[i-1]) ? (candies[i-1] + 1) : 1; } for(int i = markings.length - 2; i >= 0; i--) { candies[i] = (markings[i] > markings[i+1] && (markings[i+1] + 1) > markings[i]) ? (candies[i+1] + 1) : candies[i]; }

- S
aziron + 0 comments but what about when the adjacent enteries are equal??

ARS1997 + 0 comments [deleted]ARS1997 + 0 comments I did it in same way, and this is my explanation :

consider two arrays 'stairr'(for stair right) and 'stairl'(for stair left). Initialize it by 1.

stairr[i] contains number of consecutive decreasing elements(or ratings) on the right side of element 'i'(inclusive of element itself. So value will be >= 1). Similarly, we can define stairl[i].

Now, the reason I am using word stairs is because If we notice a candy value of particular element(or rating), it will depend on how many consecutive decreasing elements(or ratings) are on its left and right side. This 'consecutiveness' is like steps of stairs. More precisely, candy value will be maximum of both of these values. But why is it so? Because -

(i) suppose an element has stairr and stairl value 1. So we can comfortably assign its candy value as 1.

(ii) Otherwise, suppose and element 'i' has stairr[i] > stairl[i]. Now, bottom elements of both right stair and left stair will have value 1, using (i) part. We can observe that to minimize the no of candies given, each 'step up' on the stair should increase the value of candy number by 1, if possible. This can be achieved it candie value of element 'i' is stairr[i] and candy value of each element in right stair of 'i' will decrease by 1 as we go down untill it reaches the bottom, which will have value 1. Similarly, if stairl[i] > stairr[i], then candy value of element 'i' will be stairl[i].

(iii) What if two consecutive elements have equal value(or rating) ? If 'i' and 'i + 1' have equal rating, then element 'i' enforce no constraint on element 'i + 1', so it is just like as if there is no stair step on left of 'i + 1' or stairl[i + 1] = 1(just the element itself). Similarly, stairr[i] = 1.

- SC
suvamc07 + 0 comments This is exactly the right method because what we need to do is to take chunks of three at a time and compare the middle first with the value at left and then with the value at right and according to that increase the value of the middle value... In the technique discussed above when we are traversing left to right we are actually comapring the value of that middle part with its left value and when we are traversing from right to left we are actually comparing value of middle with its right value.

sgrebenkin + 0 comments Same, made 2 passes from left to right, then from right to left. All test passed. Think the variant with DP from editorial (implementation) is more complex. It's funny, but the "Problem Setter's code" is simplier and really close to my solution.

azaldin123 + 1 comment No such thing as O(2xN), it is simply a O(N) solution

hiindia_himanshu + 1 comment Here is the formal definition of Big-O:

**f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.**So,saying that there is no such thing as O(2xN) is wrong. Although, you may say that O(N)=O(2xN).sgrebenkin + 1 comment Formally g(n) could be g(n)=2*n. Therefore it's correct to say O(2*n). And we all know, O(2*n)=O(n). Both is correct.

hiindia_himanshu + 0 comments That's what I said

- RW
rwan7727 + 0 comments Passed all tests in c++:

int main() { int n; cin >> n; vector<int> r(n); // children ratings vector<int> c(n); // candies allocated to each child // take in r[] and parse left to right int numcandies=1; // num of candies to give c[0]=1; cin >> r[0]; for (int i=1;i<n;i++) { cin >> r[i]; if (r[i]>r[i-1]) numcandies++; else if (r[i]<=r[i-1]) numcandies=1; c[i]=numcandies; } // 2nd parse right to left and accumulate total numcandies=1; long total=c[n-1]; for (int i=n-2;i>=0;i--) { if (r[i]>r[i+1]) numcandies++; else if (r[i]<=r[i+1]) numcandies=1; c[i]=(numcandies>c[i]?numcandies:c[i]); //use the larger of 2 parses total+=c[i]; } cout << total; return 0; }

- PK
khushlanipiyush + 0 comments Yup! The same I have done and passed all the test cases.

pzang + 2 comments What kind of class in the world would have 100000 kids.... LOL

- RE
IronMan07 + 2 comments Virtual class or online course. ;)

bigohone + 2 comments online kindergarden

- JG
jhguo + 1 comment Kids administrated online? Wow

bigohone + 1 comment Yup, also imagine they can wear VR-cardboard and play together, or fight with each other, or cry together in a fake reality.

lol ... any ideas about ther nannies? :P

Freak_1231 + 0 comments why would anybody want to give virtual candies to virtual kids???really??this is really insulting Xd

Rumperthumskin + 0 comments Omg... "online kindergarten" made me seriously ROFL :)

- AG
agodfrey3 + 0 comments virtual kids can't sit in a line...well...not a literal line, at least ;)...perhaps a..queue?

*ba dum shh*

eFish + 0 comments they are

*tiny*kids

- A
rasputin + 2 comments I don't see why this is listed under dynamic programming.

binASL + 0 comments This is under dynamic i guess because we solving it by dividing it smaller problem (getting numbers of candies by iterating it in one direction) and then using this partial solution to iterate in reverese direction

- JH
jhallock7 + 2 comments I solved this problem differently, but with what I believe is a Dynamic Programming solution. In DP questions, you are asked to calculate F[i] for some i. In this case, F[i] is the number of candies given to child i. (Then we sum the values.) The complexity is that the value F[i] depends on other values, in this case for values of i both smaller

*and larger*. The key to Dynamic Programming is that you calculate the values F[i] in an order such that you always have the previous values (i.e., dependencies) you need. So in this problem, what values are needed to calculate F[i]? Well if Ratings[i] is a local minimum, that is, child #i has a lower rating than her neighbors, then we should give her only one candy. So her candy amount didn’t depend on other candy amounts. If Ratings[i] is a local maximum, then child #i gets one more candy than the larger amount of candy between her two neighbors. If Ratings[i] is between Ratings[i-1] and Ratings[i+1], then whichever neighbor has a lower rating, child #i gets one more candy than that neighbor. So in summary, F[i] depends on 0, 2, or 1 of the adjacent values depending on whether Ratings[i] is a local minimum, maximum, or neither, respectively. So to solve this problem, you can write helper functions is_min(), is_max(), get_next_min(), and get_next_max(), and use them to find the first two local mins; set their candies to 1. Find the single local max between them and iterate inward from the mins to the max (up the mountain), giving each child one more candy than the last. Then give the max child one more candy than the neighbor who got more than the other. Then repeat by finding the next local max and min. The other important thing is that if two neighbors have the same rating, then all the children can be split into 2 groups between them, and the two groups can be solved separately. So in a subproblem, adjacent children will never have the same rating. My solution is here: https://www.hackerrank.com/challenges/candies/submissions/code/20326952- OH
hllc4t + 0 comments Oh! I used the same approach. O(N+m) where m is the total length of descending subsequences(desc_buf's). At local max we start the buffer, at local min we release it.

n = input() a = [input() for _ in xrange(n)] c, desc_buf = [1]*n, [] for i in xrange(1, n): if a[i] < a[i-1]: if not desc_buf: desc_buf = [i-1] desc_buf.append(i) if not i == n-1: continue if a[i] > a[i-1]: c[i] = c[i-1] + 1 if desc_buf: for extra, idx in enumerate(desc_buf[::-1]): c[idx] = max(c[idx], extra + 1) del desc_buf[:] print sum(c)

- 이
opsdownn + 0 comments It's very logical, Thanks

- MD
m_eldehairy + 1 comment what i did was first create a list of troughs in the rankings array (a trough is an item which is less than or equal to both its right and left neighbors) , then for each trought i do the following :

set the number of candies at the trough to 1.

go right incrementing the number of candies by one each time until i find a ranking crest.

repeat step 2 but to the left.

its not exactly dynamic programming , but its O(N) time complexity.

but i am wandering whats the dynamic programming version of the solution.

- AS
alpha_scorpioAsked to answer + 0 comments To figure out the candies a child gets, is an equation involving the number of candies its neightbours get and this equation depends on their relative ranking. DP version is to calulate the candies count of neighbours if it hasn't been done so far and storing it and reusing again later while calculating candy count of another child. In your code, you are calculating 'c' array multiple times which you shouldn't be doing. Calculate the value once and save it.

- HC
antipyrrhus + 1 comment Here is the way I approached this problem.

Let S[i] = The length of decreasing sequence that begins with the i-th element of the given ratings array. If there is no decreasing sequence beginning at i, S[i] = 1 by default.

Let C[i] = the minimum no. of candies given to the i-th student. The ultimate solution we want is sum(C[i]) for all i.

Key insight: C[i] = S[i] for all i, EXCEPT when ratings[i] > ratings[i-1], in which case C[i] = max(S[i], C[i-1]+1).

As an example, consider a ratings array like [4, 4, 2, 3, 4, 1]. The corresponding S array would be: S = [1, 2, 1, 1, 2, 1] The corresponding C array is: C = [1, 2, 1, 2, 3, 1] Solution: sum(C) = 10.

(Also note that it is not necessary to compute S[i] from scratch for every i. If S[i-1] > 1, then S[i] = S[i-1] - 1. This improves efficiency.)

sam_bhargav + 0 comments Thanks. helped me a lot

- RS
rohansuri + 2 comments This problem also has a greedy solution. See

- RS
rsatish1110 + 0 comments [deleted] - RS
rsatish1110 + 1 comment [deleted]prateekRajput + 1 comment did u try for this i/p=5,1,3,2,1,4

gr2581 + 0 comments 11 ?

hacker_Ming + 0 comments My C solution :

int main() {

`int i, n; scanf("%d", &n); int child[n], candy[n]; for(i=0; i<n; i++) scanf("%d", (child+i)), *(candy+i) = 1; for(i=1; i<n; i++) if(*(child+i) > *(child+i-1)) *(candy+i) = *(candy+i-1) + 1; for(i=n-2; i>=0; i--) if(*(child+i) > *(child+i+1) && *(candy+i) < *(candy+i+1) + 1) *(candy+i) = *(candy+i+1) + 1; long long total = 0; for(i=0; i<n; i++) total += *(candy+i); printf("%lld", total); return 0;`

}

jai_k_yadav + 2 comments recursive solution..all test case accepted... https://code.hackerearth.com/0a9b05l

- JS
jyotman + 1 comment All test cases passed but Exception for this case 3 3 2 1 ...... Or any other case in descending order of ratings.

jai_k_yadav + 1 comment my solution for your test case is giving answer 7 and that's the correct answer....but yeah wrong for 5 4 3 2 1 (updated) thanks for pointing out

- UP
udita_p + 2 comments should not it give 6 for case [3 3 2 1] what am i missing ? please help !

almondpie + 4 comments Yes, it should give 6 (1 + 3 + 2 + 1). What help do you need?

hacker_kaif + 0 comments 1+3+2+1=7,not 6

vikaz596 + 0 comments [deleted]akash_goel + 0 comments sarcasm ;)

- EV
AceEV + 0 comments [deleted]

- EV
AceEV + 0 comments [deleted]

- DS
dsaxena + 1 comment hey, I tried ur logic but it giving wrong output for testcases #3,5, & 7. I m not getting what I missed. please help. here is my code. public class Solution {

`public static int canGet(Vector<Integer> r, Vector<Integer> c, int i){ if(r.get(i)<=r.get(i-1) && r.get(i)<=r.get(i+1)){ return 1; } if(r.get(i)<=r.get(i-1) && r.get(i)>r.get(i+1)){ if(c.get(i+1)==0){ int temp = canGet(r,c,i+1); c.set(i+1,temp); } return 1 + c.get(i+1); } if(r.get(i)>r.get(i-1) && r.get(i)<=r.get(i+1)){ if(c.get(i-1)==0){ int temp = canGet(r,c,i-1); c.set(i-1,temp); } return 1 + c.get(i-1); } if(r.get(i)>r.get(i-1) && r.get(i)>r.get(i+1)){ if(c.get(i-1)==0){ int temp = canGet(r,c,i-1); c.set(i-1,temp); } if(c.get(i+1)==0){ int temp = canGet(r,c,i+1); c.set(i+1,temp); } return 1 + Math.max(c.get(i-1),c.get(i+1)); } return 0; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int n = in.nextInt(); Vector<Integer> rank = new Vector<Integer>(n); for(int i=0;i<n;i++){ int t = in.nextInt(); rank.add(i,t); } Vector<Integer> cand = new Vector<>(n); for(int i=0;i<n;i++){ cand.add(i,0); } if(rank.get(0)<rank.get(1)){ cand.set(0,1); } if(rank.get(n-1)<=rank.get(n-2)){ cand.set(n-1,1); } if(rank.get(0)>=rank.get(1)){ int c = canGet(rank,cand,1); cand.set(0,c+1); } if(rank.get(n-1)>rank.get(n-2)){ int c = canGet(rank,cand,n-2); cand.set(n-1,c+1); } for(int i=0;i<n;i++){ if(cand.get(i)==0){ int c = canGet(rank,cand,i); cand.set(i,c); } } long result = 0; Enumeration e = cand.elements(); while(e.hasMoreElements()){ int t = (Integer)e.nextElement(); result = result + t; } System.out.println(result); }`

}

- PS
psoma74 + 1 comment Here goes a working C++ solutions with two simple for loops to traverse forward and then reverse: https://www.hackerrank.com/challenges/candies/copy-from/24279388

Core Logic to get the count is as follows:

`//start with one candy for each kid unsigned long long nTotalCandies = nTotalStudents; int nConsecutiveGreaterPos = 0; bool bTrendChanged = false; std::vector<int> Ranks(nTotalStudents,0); std::vector<int> Candies(nTotalStudents,0); //Forward Traversal std::cin>>Ranks[0]; for(int nKid = 1; nKid < nTotalStudents; ++nKid) { std::cin>>Ranks[nKid]; if((Ranks[nKid] > Ranks[nKid-1]) && (Candies[nKid] <= Candies[nKid-1])) { //update with new candies nTotalCandies += Candies[nKid-1]+1 - Candies[nKid]; Candies[nKid] = Candies[nKid-1]+1; } else if(!bTrendChanged && (Ranks[nKid] != Ranks[nKid-1]) { nConsecutiveGreaterPos = nKid-1; bTrendChanged = true; } } //Reverse traversal to update with latest candies for(int nKid = nTotalStudents-2; nKid >= nConsecutiveGreaterPos; --nKid) { if((Ranks[nKid] > Ranks[nKid+1]) && (Candies[nKid] <= Candies[nKid+1])) { //update with new candies nTotalCandies += Candies[nKid+1]+1 - Candies[nKid]; Candies[nKid] = Candies[nKid+1]+1; } }`

offero + 0 comments This is not the place for example solutions.

liju_leelives + 1 comment I used DP. The right to left and left to right solution works. But it is a lot fun if you use DP.

- Every student's candy value depends on their left and right student.
- So build the solution by calculating the neighbours value and then reccursing back to the top using:

func getMaxFromRight(int idx): //Handle base case and edge cases here if ranking[idx-1] < ranking[idx] > ranking[idx+1]; then candy[idx] = max(candy[idx-1], getMaxFromRight(idx+1))+1; else if (ranking[idx+1] < ranking[idx]) then candy[idx] = getMaxFromRight(idx+1)+1; else if (ranking[idx-1] < ranking[idx]) then candy[idx] = candy[idx-1]+1; getMaxFromRight(idx+1)+1; else candy[idx] = 1; getMaxFromRight(idx+1)+1; return candy[idx]

Note: You have to handle base case for return and also edge cases of idx-1 >=0 and idx+1 < candy.length

sainimohit23 + 0 comments thanks bro. i learned a lot from it.

WittyNotes + 3 comments Likewise did a 'brute force' approach, after trying several times to find a better 'dynamic programming' method. Is this really dynamic programming?

Here's my Java solution:

Scanner scan = new Scanner(System.in); int length = scan.nextInt(); int[] children = new int[length]; int[] candies = new int[length]; // seed children[0] = scan.nextInt(); candies[0] = 1; // search forward sequences for (int i = 1; i < length; i++){ children[i] = scan.nextInt(); candies[i] = 1; if (children[i] > children[i - 1]) candies[i] = candies[i - 1] + 1; } // search reverse sequences for (int i = length - 1; i > 0; i--){ if (children[i] < children[i - 1]) candies[i - 1] = Math.max(candies[i - 1], candies[i] + 1); } long sum = 0; for (int i= 0; i < candies.length; i++){ sum += candies[i]; } System.out.println(sum);

- MA
atiq1589 + 0 comments Thanks. Helped a lot to find the bug :)

- PP
PouyaTheDon + 1 comment Why is it that I get the wrong answer for test cases 11 and 12? do you get that as well?

- WP
williampangiawan + 0 comments You should consider the case where you get the maximum result.

- GS
gagandeep2598 + 1 comment What is the need of reverse sequence? Please explain.

WittyNotes + 0 comments To handle cases like the following:

5 4 3 2 1

Somehow, the algorithm must be 'smart' enough to know that the leftmost child will have five pieces of candy.

Sort 261 Discussions, By:

Please Login in order to post a comment