# Distribute Minimum Candies Using Greedy Algorithm in C++

Consider a given array with N integers, where each element represents the ratings of N children standing in a line. We have to distribute **minimum** candies in C++ with the greedy algorithm to these children in such a way that:

- Children with higher ratings have more candies than their neighbors and each of them must have at least one candy.

This problem is previously asked by companies Microsoft, Flipkart, Amazon.

**EXAMPLE:**

INPUT, A[] : { 6, 4, 5, 2, 1 }

OUTPUT, Minimum Candies required = 9

Explanation:

Candies given to respective children are : [2, 1, 3, 2, 1]

Sum = 2+1+3+2+1 = 9

The better way to solve this problem is by using the Greedy Algorithm.

## GREEDY APPROACH TO DISTRIBUTE MINIMUM NUMBERS OF CANDIES REQUIRED IN C++:

We will be using the Greedy approach to solve this problem. The algorithm to solve this problem is mentioned below:

- At first, We need to initialize a vector
**temp**of size N and value 1 (distribute at least one candy to each child). - Traverse the array from
**left**(i=1) to right (i=A.size()), If A[i]>A[i-1], update**temp[i]**value to**temp[i-1]+1**. - Again, Traverse the array from
**right**(i-A.size()-2) to left (i=0).**If A[i]>A[i+1]**then perform**temp[i]=max(temp[i+1]+1, temp[i]),****else**perform**temp[i]=max(temp[i], 1)**. - Now, the sum of elements of the array temp will return the minimum number of candies required.

The implementation of the above algorithm in C++:

#include <bits/stdc++.h> using namespace std; // Func to return minimum number of candies required int minCandy(vector<int> A) { int n = A.size(); //Initilize temp vector with 1 vector<int> temp(n, 1); //Traverse from left to right for (int i = 1; i < n; i++) { if (A[i] > A[i-1]) temp[i] = temp[i-1] + 1; } // Traverse from right to left for (int i = n-2; i >= 0; i--) { if (A[i] > A[i + 1]) temp[i] = max(temp[i+1] + 1, temp[i]); else temp[i] = max(temp[i], 1); } int sum = 0; // Sum of elements of temp vector to find the required sum for (int i = 0; i < temp.size(); i++) { sum += temp[i]; } //Return final answer return sum; } int main() { vector<int> A = { 6, 4, 5, 2, 1 }; //Calling the function and printing the answer cout<<"Minimum Candies required = " << minCandy(A); }

Output:

Minimum Candies required = 9

**Time Complexity:** O(n)

Also, refer:

## Leave a Reply