# Distribute Candy

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Distribute Candy

There are N children lined up in a row. A rating value is issued to each child.

The task is to find the minimum number of candies required for distributing to N children, given an array arr[] containing N positive integers representing the ratings of N children, such that each child receives at least one candy and children with higher ratings receive more candies than their neighbors.

Examples:
Input: arr[] = {1, 0, 2}
Output: 5
Explanation:
Consider the distribution of candies as {2, 1, 2} that satisfy the given conditions. Therefore, the sum of candies is 2 + 1 + 2 = 5, which is the minimum required candies.

### Greedy Approach

The Greedy Approach can be used to tackle the following problem.

1. Initialize an array, say ans[] to store the amount of candies assigned to every child, and initialize it with 1 to every array element ans[].

2. Traverse the given array arr[] and if the value of arr[i + 1] is greater than arr[i] and the value of ans[i + 1] is at least ans[i], then update the value of ans[i + 1] as ans[i] + 1.

3. Traverse the given array from the back and perform the following steps:

4. If the value of arr[i] is greater than arr[i + 1] and the value of ans[i] is at least ans[i + 1], then update the value of ans[i + 1] as ans[i] + 1.

5. If the value of arr[i] is equal to arr[i + 1] and the value of ans[i] is less than ans[i + 1], then update the value of ans[i + 1] as ans[i] + 1.

6. After completing the above steps, print the sum of array ans[] as the resultant sum of candies.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;
int countCandies(int arr[], int n)
{

int sum = 0;
int ans[n];

if (n == 1) {
return 1;
}

for (int i = 0; i < n; i++)
ans[i] = 1;

for (int i = 0; i < n - 1; i++) {

if (arr[i + 1] > arr[i]
&& ans[i + 1] <= ans[i]) {

ans[i + 1] = ans[i] + 1;
}
}

for (int i = n - 2; i >= 0; i--) {

if (arr[i] > arr[i + 1]
&& ans[i] <= ans[i + 1]) {

ans[i] = ans[i + 1] + 1;
}

else if (arr[i] == arr[i + 1]
&& ans[i] < ans[i + 1]) {

ans[i] = ans[i + 1] + 1;
}

sum += ans[i];
}

sum += ans[n - 1];

return sum;
}

int main()
{
int arr[] = { 1, 0, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countCandies(arr, N);

return 0;
}
```

Java Implementation:

```import java.io.*;

class Main{

static int countCandies(int arr[], int n)
{

int sum = 0;

int[] ans = new int[n];

if (n == 1)
{
return 1;
}

for(int i = 0; i < n; i++)
ans[i] = 1;

for(int i = 0; i < n - 1; i++)
{

if (arr[i + 1] > arr[i] &&
ans[i + 1] <= ans[i])
{

ans[i + 1] = ans[i] + 1;
}
}

for(int i = n - 2; i >= 0; i--)
{
if (arr[i] > arr[i + 1] &&
ans[i] <= ans[i + 1])
{

ans[i] = ans[i + 1] + 1;
}

else if (arr[i] == arr[i + 1] &&
ans[i] < ans[i + 1])
{

ans[i] = ans[i + 1] + 1;
}

sum += ans[i];
}

sum += ans[n - 1];

return sum;
}

public static void main(String[] args)
{
int arr[] = { 1, 0, 2 };
int N = arr.length;

System.out.println(countCandies(arr, N));
}
}
```

Python Implementation:

```def countCandies(arr, n):

sum = 0

ans = [1] * n

if (n == 1):
return 1

for i in range(n - 1):
if (arr[i + 1] > arr[i] and
ans[i + 1] <= ans[i]):

ans[i + 1] = ans[i] + 1
for i in range(n - 2, -1, -1):
if (arr[i] > arr[i + 1] and
ans[i] <= ans[i + 1]):

ans[i] = ans[i + 1] + 1

elif (arr[i] == arr[i + 1] and
ans[i] < ans[i + 1]):

ans[i] = ans[i + 1] + 1

sum += ans[i]

sum += ans[n - 1]

return sum

if __name__ == '__main__':

arr = [ 1, 0, 2 ]
N = len(arr)

print (countCandies(arr, N))
```

Time Complexity: O(N)
Auxiliary Space: O(N)

With this article at Logicmojo, you must have the complete idea of solving Distribute Candy problem.