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:

  1. At first, We need to initialize a vector temp of size N and value 1 (distribute at least one candy to each child).
  2. 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.
  3. 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).
  4. 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

Your email address will not be published. Required fields are marked *