candies - interviewstreet

Question

Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.

Input

The first line of the input is an integer N, the number of children in Alice's class. Each of the following N lines contains an integer indicates the rating of each child.

Output

On the only line of the output print an integer describing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Output

4

Explanation

The number of candies Alice must give are 1,2 and 1.

Constraints:

N and the rating of each children is no larger than 10^5.

Can anyone please help me?

Answer 1

You can do this in two passes. Start with everyone having one candy.

First loop i from 1 to n-1 (zero based), if rating[i] > rating[i-1] then candies[i] = candies[i-1]+1

Then loop i from n-2 to 0; if rating[i] > rating[i+1] then candies[i] = max(candies[i], candies[i+1]+1)

It's pretty easy to show this gives you a valid distribution of candies, since the second loop can't break anything fixed by the first, and all possible rating discrepancies must be caught by one of the two loops. It's not as obvious that this will use the minimum number of candies, but if you examine each assignment closely you can show that the conditions prove a lower bound on the number of candies required (by a particular individual) at each step.

Answer 2

To make the analysis of this algorithm more interesting I will the following input:

9
2
3
4
4
4
2
1
3
4

Firstly, notice if a kid sits next to a kid who is getting x candies and that kid has a lower rating then the first kid should get at least x+1 candies. Making the difference more than 1 will just waste candies. The difference sometimes must be greater than 1, but I'll get to when that happens later.

Now on to finding the kids who should get only one candy. I visualise the ratings as a mountain range (The greater the rating the higher the mountains at that point) and finding the kids who should get one candy as finding valleys (points where both neighbours have a higher rating or the same rating) in the mountain range. The example given would look like (the valleys are indicated by the arrows):

  ***   *
 ****  **
****** **
*********
^  ^  ^

For the purpose of this process I assume there are 2 peaks of "infinite" height before the beginning and after the end of this line. (When I say infinite I just mean larger than any possible value in the input so you can just use 10^5+1 for "infinity". In practice, I'd use a value larger than that in case the problem setters have bugged input data.)

You can easily find the valleys using the following code:

ratings = ...
N = ...
valleys = []

def get_rating(i):
    if i < 0 or i > N-1:
        return INFINITY
    return ratings[i]

for i from 0 to N-1:
    if get_rating(i) <= get_rating(i-1) and get_rating(i) <= get_rating(i+1):
        valleys.append(i)

The array valleys contains the indices of the valleys. We know each kid representing a valley should get one candy. For illustration assume the valley is at index 4. Now we know the kids at index 3 and 5 should get at least 2 candies. If the kid at index 2 has a higher rating than the kid at index 3 that kid should get at least 3 candies. And so on for 2 and down. Similarly for 6 and up.

Note I say "at least", this is because of peaks (kids whose ratings are higher than both of their neighbour's, note unlike valleys I don't include equality in this definition). Peaks can have two minimum constraints and we simply choose the greater of the two.

Now we can find the number of candies each kid should get with the following code:

candies = [0] * N # An array of N 0s
for valley_idx in valleys:
    candies[valley_idx] = 1

    cur_idx = valley_idx-1
    cur_candies = 2
    while cur_idx >= 0 and ratings[cur_idx] > ratings[cur_idx+1]:
        candies[cur_idx] = max(candies[cur_idx], cur_candies)
        cur_idx -= 1
        cur_candies += 1

    cur_idx = valley_idx+1
    cur_candies = 2
    while cur_idx < N and ratings[cur_idx] > ratings[cur_idx-1]:
        candies[cur_idx] = max(candies[cur_idx], cur_candies)
        cur_idx += 1
        cur_candies += 1

Then the number of candies the teacher needs to buy is the sum of the values in the candies array.

Doing this the answer turns out to be 18 for our sample input or in the form of a graph:

  * *   *
 ** ** **
*********

Solution to slightly altered problem statement

In the above solution I assumed that adjacent kids with the same rating don't place any restrictions on the amount of candy either should get with relation to the other. If it is instead the case that both kids need to get the same amount of candy we can quite easily alter the algorithm to take this into account.

The basic idea is that we do a sort of run length encoding, because we can notice that whether there are 1 or more kids in a row that have the same rating it doesn't alter the amount of candies their neighbours should get. We need to keep track of the number of kids in a row though since 5 kids in a row getting 5 candies means we have to dole out 25 candies and not just 5. We do this with a multipliers array. Using the following code we find the new ratings array and the multipliers array:

new_ratings = [ratings[0]]
multipliers = [1]
for i from 1 to N-1:
    if ratings[i] == new_ratings[len(new_ratings)-1]:
        multipliers[len(new_ratings)-1] += 1
    else:
        new_ratings.append(ratings[i])
        multipliers.append(1)

Now we just run the original algorithm on the new_ratings array and get a candies array. Then to get the actual amount of candies we can just run:

answer = 0
for i from 0 to len(new_ratings)-1:
    answer += multipliers[i] * candies[i]

Doing this the answer turns out to be 20 for our sample input or in the form of a graph:

  ***   *
 ***** **
*********

Answer 3

I used simple DP approach to solve this problem. Increment the ith value in DP table if u get the rating greater than previous one, else there might be two conditions. One condition is DP value of previous index is 1 then traverse in reverse order till you get value lesser than its next value and keep updating the DP. A another condition is DP value of previous index is greater than 1, in that case present index in DP is assigned 1.

for(int i=1; i <= n; i++){
    scanf("%d", ra+i);
    if( ra[i] > ra[i-1] )
        dp[i] = dp[i-1] + 1;
    else if( dp[i-1] == 1 ){
        dp[i] = 1;
        for( int j=i-1; j>0; j-- )
            if( ra[j] > ra[j+1] )
                dp[j] = max ( dp[j+1] + 1, dp[j] );
            else
                break;
    }       
    else
        dp[i] = 1;
}
long long sum = 0;
for(int i = 1;i <= n; i++)sum+= dp[i];
printf("%lld\n",sum);

Answer 4

Actually this question can be solved by passing two times over the array. And the solution will be O(N) time. I solved this problem by using geeksforgeeks Trapping Rain Water (http://www.geeksforgeeks.org/trapping-rain-water/ ) problem. Same principles can be applied to this questions.

First of all we have two rules. - Each student gets at least 1 candy. - Each student who has a better rating than his/her neighbor (the next or the previous student) he will get at least one more candy then them.

Just as I've said we need two passing over the array. The first one will be from left to right; - At first we will assign one candy to the first one. - Then loop over the array by checking if current one has bigger rating then give him one more than the previous student, otherwise give him 1 candy.

The second pass will be from right to left. - This time we start by assigning one candy to the last one. - Then loop over the array from right to left and do the similar things just in the first loop.

After this two loops, we will loop over right and left by getting the maximum of the array and add this value to the total candies.

    Test cases :
    input  : { 1, 2, 2 }
    output : { 1, 2, 1 } => 4 
    input  : { 9, 2, 3, 4, 4, 4, 2, 1, 3, 4 }
    output : { 2, 1, 2, 3, 1, 3, 2, 1, 2, 3 } => 20

Below you can find a Java solution for this problem.

public int calculate(int[] arr) {
    int m = arr.length;
    int[] left = new int[m];
    int[] right = new int[m];
    int candies = 0;
    left[0] = 1;
    for (int i = 1; i < m; i++)
        left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
    right[m - 1] = 1;
    for (int i = m - 2; i >= 0; i--)
        right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
    for (int i = 0; i < m; i++)
        candies += Math.max(left[i], right[i]);
    return candies;
}

Answer 5

Let's say We have

1, 5, 2, 10, 10 3, 8, 9 , 1 , 1, 2 as ratings of 11 students S1 to S11

Let us say we make a graph rating vs student where rating is plotted on y axis, then

1. Local minimas will always get one candy, so student S1 , S3, S6, S9 and S10 will be local minimas and will get one candy. We can argue by saying there is a minimum solution (So) which deviate from what we say, then we can create one more solution (So1) where all the students get same candy and local minima which deviates gets one candy, then So1 will be minimum, so therefore there can be no minimum solution where local minimas get candies more than 1.

2. Once you have got values of local minimas, you can transverse left and right of the minima to calculate candies of other students.

3. For local maxima , it will be greater of value for its adjacent nodes +1. Working code is below, time complexity is O(n) and space complexity is O(n)

   public static int candy(ArrayList<Integer> a) {
       int size = a.size();
       int[] cand = new int[size];
   
       // give all children candies equal to 1
       // local minimas will get 1
       for(int i = 0; i < size; i++)
       {
           cand[i] = 1;
       }     
       // increase count on the right of local minimas
       for(int i = 1; i < size; i++)
       {
           if(a.get(i) > a.get(i-1))
           {
               cand[i] = cand[i-1]+1;
           }
       }
       // increase count on the left of local minimas
       // local maximas should be max of left and right
       for(int i = size-2; i >= 0; i--)
       {
           if(a.get(i) > a.get(i+1))
           {
               cand[i] = Math.max(cand[i], cand[i+1]+1);
           }
   
       }
   
       // get the sum
       int count = 0;
       for(int i = 0; i < size; i++)
       {
           count = count + cand[i];
       }
       return count;
   }
   

You can test with test cases at HackerEarth Problem : https://www.hackerrank.com/challenges/candies

Leetcode : https://leetcode.com/problems/candy/

You can find more detailed explanation of why this works @ http://stackandqueue.com/?p=108

Answer 6

A very easy implementation

Space Complexity: O(n) Time Complexity : O(n)

Step 1: Start traversing the array from left to right and assign the value 1 to each index in dp array.

Step 2: Start traversing the array from left to right and if the person scored more marks then the person sitting to his left then dp of that person will be dp[i-1]+1;

Step 3: Start traversing the array from right to left and if the person scored more marks then the person sitting to his right then dp of that person will be max(dp[i],dp[i+1]+1);

Step 4 : Add all the values in dp array.

#include<bits/stdc++.h>
using namespace std;
long int arr[100005];
long int dp[100005];
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%ld",&arr[i]);
    long int ans=0;
    dp[0]=1;
    for(i=1;i<n;i++)
         {
            if(arr[i]>arr[i-1])
                dp[i]=dp[i-1]+1;
            else
                dp[i]=1;
         }
      for(i=n-2;i>=0;i--)
      {
          if(arr[i]>arr[i+1])
            dp[i]=max(dp[i],dp[i+1]+1);
      }
     for(i=0;i<n;i++)
     {
         ans=ans+dp[i];
     }
    cout<<ans<<endl;
    return 0;
}

Answer 7

I felt this may be one of the possible solutions...

def candy(N,r):
    H=[0]*N
    R=r
    cur_can=1
    cand=[0]*N
    cand[0]=1
    #print R#,'\n',cand
    for i in range(0,N):
        if i!=0:
            #print R[i],'  ',R[i-1]
            if R[i]>R[i-1]:
                cand[i]=cand[i-1]+1
            else:
                cand[i]=1
##            print R[i],i
    sum=0
##    print i
    print cand
    for j in range(0,N):
        sum+=cand[j]
    return sum
r=[1,2,2,4,1,2,4]
N=len(r)
print candy(N,r)

The output for the values used as a sample in th codes gives 12 as the answer, which seems right to me... What do you think?

Answer 8

I don't think this is a very difficult problem. If you think of it carefully, you will get you own answer.

#include <iostream>
#include <queue>

using namespace std;

#define CALC(n) (n)+(n)*((n)-1)/2

struct PAIR {
int n;int up;//up=0,1,2; 0是升，1是平，2是降
public:
PAIR(int _n,int _u){
    n=_n;up=_u;
}
};

int N;

queue<PAIR> q;

int calc(int up,int p){
    if(up==1)
        return p;
    else {
        return p+p*(p-1)/2;
    }
}

int getType(int lc,int c){
    int up=-1;
    if(c>lc)
    up=0;
    else if(c==lc)
    up=1;
else
    up=2;
return up;
}

int main(int argc, const char * argv[])
{
scanf("%d",&N);
int lastChild,child,n=2;
long long result=0;
scanf("%d%d",&lastChild,&child);N-=2;
int up=getType(lastChild, child);
lastChild=child;
while (N--) {
    scanf("%d",&child);
    int tu=getType(lastChild, child);
    if(tu==up)
        n++;
    else {
        q.push(PAIR(n,up));
        n=2;
        up=tu;
    }
    lastChild=child;
}
q.push(PAIR(n,up));
q.push(PAIR(1,1));
/*其实主要就是看转折点是属于上一段还是当前段。
 如果是正V的话，转折点属于后一段。前一段的和-1.
 如果是倒V的话，转折点属于长的一段。
 然后是平的和别的有搭配的话，转折点属于别的
 */
PAIR lastp=q.front();q.pop();
while(q.size()){
    PAIR pir=q.front();q.pop();
    if(pir.up==1){
        result+=calc(lastp.up,lastp.n);//如果下一段是平的，就把转折点分到上一段
        pir.n-=1;
    }
    else if(lastp.up==1){
        result+=calc(lastp.up,lastp.n-1);//如果上一段是平的，就把转折点分到下一段
    } else if((lastp.up==0)&&(pir.up==2)){//如果是倒V型的，转折点属于长的
        if(lastp.n>pir.n){
            result+=calc(lastp.up,lastp.n);
            pir.n-=1;
        } else {
            result+=calc(lastp.up,lastp.n-1);
        }
    } else if((lastp.up==2)&&(pir.up==0)){//如果是正V型的，转折点属于后一个
        result+=calc(lastp.up,lastp.n)-1;
    } else {
        printf("WRONG!");
    }
    lastp=pir;
}
printf("%lld\n",result);
return 0;
}

Answer 9

I used two queues to store increasing and decreasing sequences of unassigned indices and enumerate all possible situations of the adjacent ratings and assign the candies when rating hit a plateau or bottom(i.e. when current rating is local minimum or same as previous).

Here is my solution:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <deque>

void assigncandies(std::deque<int>& incr, std::deque<int>& decr, unsigned int& total) {
  int incrlen = incr.size();
  int decrlen = decr.size();
  if (incrlen >= decrlen) {
    int num=incrlen;
    int last = incr.back();
    while(!incr.empty()) { 
      int idx = incr.back();
      total += num;
      incr.pop_back();
      num --;
    }
    if (!decr.empty()) {
      if (last == decr.front()) decr.pop_front(); 
      num=1;
      while(!decr.empty()) {
       int idx = decr.back();
        //candies[idx]=num;
        total += num;
        decr.pop_back();
          num ++;
      }
    }
  } else {
    int num=decrlen;
    int last = decr.front();
    while (!decr.empty()) {
      int idx = decr.front();
      //candies[idx]=num;
      total += num;
      decr.pop_front();
      num --;
    }
    if (!incr.empty()) {
      if (last == incr.back()) incr.pop_back();
      num=1;
      while(!incr.empty()) {
        int idx = incr.front();
        //candies[idx]=num;
        total += num;
        incr.pop_front();
          num ++;
      }
    }
  }
}

int main () {
  int N;
  unsigned int total=0;
  int PrevR, CurR, NextR;
  std::cin >> N;
  std::deque<int> incr;
  std::deque<int> decr;
  for (int i = 0; i<N;i++) {
    if (i==0) {
      std::cin>>CurR;
      std::cin >> NextR;
    } else if (i != N-1) std::cin >> NextR;

    if (i==0) {
      if (CurR>NextR) decr.push_back(0);
      else if (CurR<NextR) incr.push_back(0);
      else total=1;
    } else if (i==N-1) {
      if (PrevR<CurR) {
        incr.push_back(i);
      }
      if (PrevR>CurR) {
        decr.push_back(i);
      }
      if (PrevR==CurR) {
        total += 1;
      }
      assigncandies(incr,decr,total);
    } else {
      if (PrevR == CurR && CurR == NextR) {
        assigncandies(incr,decr,total);
        total += 1;
      }
      if (PrevR == CurR && CurR < NextR) {
        assigncandies(incr,decr,total);
        incr.push_back(i);
      }
      if (PrevR == CurR && CurR > NextR) {
        assigncandies(incr,decr,total);
        decr.push_back(i);
      }
      if (PrevR < CurR) {
        incr.push_back(i);
        if (CurR > NextR) decr.push_back(i);
      }
      if (PrevR > CurR && CurR >= NextR) {
        decr.push_back(i);
      }
      if (PrevR > CurR && CurR < NextR) {
        decr.push_back(i);
        assigncandies(incr,decr,total);
        total -= 1;
        incr.push_back(i);
      }
    }
    PrevR = CurR;
    CurR = NextR;
  }

  std::cout<<total<<std::endl;
  return 0;
}

It passes the testcases and 3/10 cases correct but I got segmentation fault for the rest.
I am wondering whether anyone can point out what is wrong with my code.
Thank you very much!

Answer 10

Perhaps the simplest solution:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

int children;
int sum=0;

cin >> children;
int ratings[children];
int candies[children];

//give all children 1 candy to start
for(int i=0;i<children;++i)
{
     cin >> ratings[i];  
     candies[i] = 1;
}

//if the current child has a better rating than the child
//before him he is entitled to +1 greater candy than that child
for(int i=1;i<children;++i) 
{
     if(ratings[i] > ratings[i-1])
         candies[i] = candies[i-1]+1;
}

// work backwards to break any discrepancies ex.
// rating[5,4,3] -> candies[1,1,1] -> candies [1,1,1] -> candies [3,2,1]
// starting ratings  give everyone 1   first loop         second loop
for(int i=children-1;i>=0;--i)
{
     if(ratings[i] > ratings[i+1])
     {
          candies[i] = max(candies[i],candies[i+1]+1);   
     }
}

for(int i=0;i<children;++i)
{ 
     sum+=candies[i];
}

cout << sum;
return 0;

}

Answer 11

1.Initialize Ratings[] with the given ratings.

2.We'll first give 1 Candy to each of the children. So initialize all members in Val[] with 1.

3.Now traverse through and check with the 2 adjacent children (i + 1 and i - 1) whether the condition is held.

4.Keep doing this until we get an entire traversal where the condition is never broken. We're done then!

bool done = false;
while (!done) 
{
    done = true;
    for (int i = 0 to i = Ratings.size() - 1) 
    {
        for (int k = 1 and k = -1) 
        {
            int adjacent = i + k;
            if (adjacent >= 0 && adjacent < N) 
            {
                if (Ratings[adjacent] > Ratings[i] && Val[adjacent] <= Val[i]) 
                {                       
                    Val[adjacent] = Val[i] + 1;
                    done = false;
                }
            }
        }
    }

}

Answer 12

# this python code solves the problem for all test cases on interviewstreet

#!/usr/bin/python

if __name__ == "__main__":
N = int(raw_input().strip())
scores = []
for i in range(N):
    scores.append(int(raw_input().strip()))
nc = []
if(scores[0]>scores[1]):
    nc.append(-1)
    else:
    nc.append(0)
    for i in range(1,N-1):
        if (scores[i] > scores[i-1]) and (scores[i]>scores[i+1]):
        nc.append(2)
    elif (scores[i] > scores[i-1]):
        nc.append(1)
    elif (scores[i]>scores[i+1]):
        nc.append(-1) 
    else:
        nc.append(0)

    if(scores[N-1]> scores[N-2]):
        nc.append(1)
    else:
    nc.append(0)

    noc = []
    for i in range(N):
    noc.append(0)

    for i in range(N):
    if(nc[i]==0):
            noc[i] = 1

    for i in range(N):
    if(nc[i]==1) and (noc[i-1]!=0):
        noc[i] = noc[i-1]+1 

    for i in range(N-1,-1,-1):
    if(nc[i]==-1) and (noc[i+1]!=0):
        noc[i] = noc[i+1]+1

    for i in range(N):
    if(nc[i]==2) and (noc[i-1]!=0) and (noc[i+1]!=0):
        noc[i] = max((noc[i-1],noc[i+1]))+1 
    nt = sum(noc)


    print nt

Answer 13

Think of these possible rating configurations: 1 2 3 4 5 or any increasing sequence and 5 4 3 2 1 or any decreasing sequence

what can be done in the first case? 1 2 3 4 5 is the candies that are allocated in the second case the candies are 5 4 3 2 1

The solution can be obtained by scanning the array from left to right and identifying intervals of increase and scanning from right to left and again identifying intervals of increase & allocating minimal amounts of candies in this process. for exact details, please look at the code:

#include <stdio.h>
#include <algorithm>
using namespace std;

#define N 100000

int c[N];
int val[N];

int solve(int n)
{
  int res=n;
  int i=0,value=0;
  while(i<n)
  {
    value=0;
    i+=1;
    while(i<n && c[i]>c[i-1])
    {
      value+=1;
      val[i]=value;
      i+=1;
    }
  }

  i=n-1;
  while(i>=0)
  {
    value=0;
    i-=1;
    while(i>=0 && c[i]>c[i+1])
    {
      value+=1;
      val[i]=max(val[i],value);
      i-=1;
    }
  }

  for(i=0;i<n;++i) res+=val[i];

  return res;
}

int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;++i) scanf("%d",&c[i]);
  printf("%d\n",solve(n));
  return 0;
}

Answer 14

To summarize:

#include <vector>
#include <iostream>
using namespace std;

int main() {
    int N;
    cin>>N;
    vector<int> A(N,0),B(N,1);
    for(int i=0;i<N;++i) cin>>A[i];
    for(int i=0;i<N;++i) if(A[i]>A[i-1]) B[i]=B[i-1]+1;
    for(int j=N-2;j>=0;--j) if (A[j]>A[j+1]) B[j] = max(B[j], B[j+1]+1);
    int sum=0;
    for(int i=0;i<N;++i) sum+=B[i];
    cout<<sum<<endl;
    return 0;
}

Answer 15

Simple working code with an array as input, in Java language. Time Complexity: O(n).

import java.util.Arrays;
public class MyClass {
    public static void main(String[] args) {
        int []childrenRating = {9, 8, 7, 10, 11, 12, 14, 1, 5};
        int []expectedDistribution = {3, 2, 1,  2,  3,  4,  5, 1, 2};
        int []resultingDistribution = new int[childrenRating.length];
        int v = 1;
        int k, j = 0;
        while(j < childrenRating.length){
            k = j;
            if(k >0 && childrenRating[k] == childrenRating[k-1]) { v=1; } 
            resultingDistribution[k] = v;
            while(j+1 < childrenRating.length && childrenRating[j+1] < childrenRating[j]){
                j++;
            }
            v = 1;
            for(int i = j; i > k; i--){
                resultingDistribution[i] = v++; 
            }
            resultingDistribution[k] = Math.max(resultingDistribution[k], v);
            j++;
            v = resultingDistribution[j-1]+1;
        }
        if(Arrays.equals(expectedDistribution, resultingDistribution)) {
            System.out.println("Correct Distribution");
        }
        else {
            System.out.println("Wrong Distribution!");
        }
    }
}

Answer 16

AS mentioned by others,scanning left to right and then right to left,and getting max candies used at certain postion is working.

Before this, i used other way,which seemed to be working and i checked it with many different inputs,although i couldnt clearly write it in code,Here is the Algo:

Algorithm:
1.Use an int[]index array  and store all the indexes in the sorted value of thie ranks.

so here
int values[]=9 2 3 6 5 4 3 2 2 2
so index sorted array would be
int index[]= 1 7 8 9 2 6 5 4 3 0


now int[] result=new result[10];
and initialize it with -1.

sending each value from index[]in the order and make sure that each one is satifying the given condtions.
that

i=index;
while(i>=0)
{
if(i-1>=0 && arr[i]>arr[i-1])
break;
if(i-1>=0 && arr[i]<arr[i-1])
result[i-1]=result[i]+1;
else
if(i-1>=0 && arr[i]==arr[i-1])
 result[i-1]=1
 i--;
}

//similary towards the right

i=index;
while(i<arr.length)
{
if(i+1<arr.length && arr[i]>arr[i+1])
break;
if(i+1<arr.length && arr[i]<arr[i+1])
 result[i+1]=1+result[i];
else
if(i+1<arr.length && arr[i]==arr[i+1])
 result[i+1]=1

 i++;
}


so result array will be like this for index 1

2 1 2 3 - - - - - -

then for index 7
2 1 2 5(its modifed from 3) 4 3 2 1 1

followe by indeices :8 9 2 6 5 4 3 0 

which all satifies the condtion and more modification occurs in this case..so total number of candies =22