Minimum number of candies required to distribute among children based on given conditions
Given an array arr[] consisting of N positive integers representing the ratings of N children, the task is to find the minimum number of candies required for distributing to N children such that every child gets at least one candy and the children having the higher rating get more candies than its neighbours.
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.
Input: arr[] = {1, 2, 2}
Output: 4
Approach: The given problem can be solved by using the Greedy Approach. Follow the steps below to solve the problem:
- 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[].
- Traverse the given array arr[] and if the value of arr[i + 1] is greater than arr[i], then update the value of ans[i + 1] as ans[i] + 1.
- Traverse the given array from the back and perform the following steps:
- If the value of arr[i] is greater than arr[i + 1] and the value of ans[i] is less than or equal to ans[i + 1], then update the value of ans[i] as ans[i + 1] + 1.
- After completing the above steps, print the sum of array ans[] as the resultant sum of candies.
Below is the implementation of the above approach:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the minimum number
// of candies that is to be distributed
int countCandies(int arr[], int n)
{
// Stores total count of candies
int sum = 0;
// Stores the amount of candies
// allocated to a student
int ans[n];
// If the value of N is 1
if (n == 1) {
return 1;
}
// Initialize with 1 all array
// element
for (int i = 0; i < n; i++)
ans[i] = 1;
// Traverse the array arr[]
for (int i = 0; i < n - 1; i++) {
// If arr[i+1] is greater than
// arr[i]
if (arr[i + 1] > arr[i]) {
// Assign ans[i]+1 to
// ans[i+1]
ans[i + 1] = ans[i] + 1;
}
}
// Iterate until i is atleast 0
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is greater than
// arr[i+1] and ans[i] is
// at most ans[i+1]
if (arr[i] > arr[i + 1] && ans[i] <= ans[i + 1]) {
// Assign ans[i+1]+1 to
// ans[i]
ans[i] = ans[i + 1] + 1;
}
// Increment the sum by ans[i]
sum += ans[i];
}
sum += ans[n - 1];
// Return the resultant sum
return sum;
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countCandies(arr, N);
return 0;
}
// Java program for the above approach
import java.io.*;
class GFG {
// Function to count the minimum number
// of candies that is to be distributed
static int countCandies(int arr[], int n)
{
// Stores total count of candies
int sum = 0;
// Stores the amount of candies
// allocated to a student
int[] ans = new int[n];
// If the value of N is 1
if (n == 1) {
return 1;
}
// Initialize with 1 all array
// element
for (int i = 0; i < n; i++)
ans[i] = 1;
// Traverse the array arr[]
for (int i = 0; i < n - 1; i++) {
// If arr[i+1] is greater than
// arr[i]
if (arr[i + 1] > arr[i]) {
// Assign ans[i]+1 to
// ans[i+1]
ans[i + 1] = ans[i] + 1;
}
}
// Iterate until i is atleast 0
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is greater than
// arr[i+1] and ans[i] is
// at most ans[i+1]
if (arr[i] > arr[i + 1]
&& ans[i] <= ans[i + 1]) {
// Assign ans[i+1]+1 to
// ans[i]
ans[i] = ans[i + 1] + 1;
}
// Increment the sum by ans[i]
sum += ans[i];
}
sum += ans[n - 1];
// Return the resultant sum
return sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 0, 2 };
int N = arr.length;
System.out.println(countCandies(arr, N));
}
}
// This code is contributed by patel2127
# Python3 program for the above approach
# Function to count the minimum number
# of candies that is to be distributed
def countCandies(arr, n):
# Stores total count of candies
sum = 0
# Stores the amount of candies
# allocated to a student
ans = [1] * n
# If the value of N is 1
if (n == 1):
return 1
# Initialize with 1 all array
# element
# for (i = 0 i < n i++)
# ans[i] = 1
# Traverse the array arr[]
for i in range(n - 1):
# If arr[i+1] is greater than
# arr[i]
if (arr[i + 1] > arr[i]):
# Assign ans[i]+1 to
# ans[i+1]
ans[i + 1] = ans[i] + 1
# Iterate until i is atleast 0
for i in range(n - 2, -1, -1):
# If arr[i] is greater than
# arr[i+1] and ans[i] is
# at most ans[i+1]
if (arr[i] > arr[i + 1] and
ans[i] <= ans[i + 1]):
# Assign ans[i+1]+1 to
# ans[i]
ans[i] = ans[i + 1] + 1
# Increment the sum by ans[i]
sum += ans[i]
sum += ans[n - 1]
# Return the resultant sum
return sum
# Driver Code
if __name__ == '__main__':
arr = [1, 0, 2]
N = len(arr)
print(countCandies(arr, N))
# This code is contributed by mohit kumar 29
using System;
public class GFG {
// Function to count the minimum number
// of candies that is to be distributed
static int countCandies(int[] arr, int n)
{
// Stores total count of candies
int sum = 0;
// Stores the amount of candies
// allocated to a student
int[] ans = new int[n];
// If the value of N is 1
if (n == 1) {
return 1;
}
// Initialize with 1 all array
// element
for (int i = 0; i < n; i++)
ans[i] = 1;
// Traverse the array arr[]
for (int i = 0; i < n - 1; i++) {
// If arr[i+1] is greater than
// arr[i]
if (arr[i + 1] > arr[i]) {
// Assign ans[i]+1 to
// ans[i+1]
ans[i + 1] = ans[i] + 1;
}
}
// Iterate until i is atleast 0
for (int i = n - 2; i >= 0; i--) {
// If arr[i] is greater than
// arr[i+1] and ans[i] is
// at most ans[i+1]
if (arr[i] > arr[i + 1]
&& ans[i] <= ans[i + 1]) {
// Assign ans[i+1]+1 to
// ans[i]
ans[i] = ans[i + 1] + 1;
}
// Increment the sum by ans[i]
sum += ans[i];
}
sum += ans[n - 1];
// Return the resultant sum
return sum;
}
// Driver Code
static public void Main()
{
int[] arr = { 1, 0, 2 };
int N = arr.Length;
Console.WriteLine(countCandies(arr, N));
}
}
// This code is contributed by rag2127
// Javascript program for the above approach
// Function to count the minimum number
// of candies that is to be distributed
function countCandies(arr, n)
{
// Stores total count of candies
let sum = 0;
// Stores the amount of candies
// allocated to a student
let ans = new Array(n);
// If the value of N is 1
if (n == 1)
{
return 1;
}
// Initialize with 1 all array
// element
for(let i = 0; i < n; i++)
ans[i] = 1;
// Traverse the array arr[]
for(let i = 0; i < n - 1; i++)
{
// If arr[i+1] is greater than
// arr[i]
if (arr[i + 1] > arr[i])
{
// Assign ans[i]+1 to
// ans[i+1]
ans[i + 1] = ans[i] + 1;
}
}
// Iterate until i is atleast 0
for(let i = n - 2; i >= 0; i--)
{
// If arr[i] is greater than
// arr[i+1] and ans[i] is
// at most ans[i+1]
if (arr[i] > arr[i + 1] &&
ans[i] <= ans[i + 1])
{
// Assign ans[i+1]+1 to
// ans[i]
ans[i] = ans[i + 1] + 1;
}
// Increment the sum by ans[i]
sum += ans[i];
}
sum += ans[n - 1];
// Return the resultant sum
return sum;
}
// Driver Code
let arr = [ 1, 0, 2 ];
let N = arr.length;
console.log(countCandies(arr, N))
// This code is contributed by unknown2108
Output :- 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach: The given problem can be solved by using the Dynamic programming. Follow the steps below to solve the problem:
We can define a dynamic programming array dp[] of size N to store the minimum number of candies needed for distributing to the first i children so that each child receives at least one candy and children with higher ratings receive more candies than their neighbours. At first, we set all of the values in dp[] to 1.
Then, from left to right, we traverse the array arr[] and update the values in dp[] as follows:
- Set dp[i] to dp[i-1] + 1 if the current child has a higher rating than its left neighbour.
- Set dp[i] to 1 if the current child has a lower or equal rating than its left neighbour.
Following the update of the values in dp[] from left to right, we traverse the array arr[] from right to left and update the values in dp[] once more as follows:
- If the current child has a higher rating than its right neighbor, set dp[i] to max(dp[i], dp[i+1] + 1).
Finally, we compute the sum of all values in dp[], which gives us the required number of candies.
#include <iostream>
#include <vector>
using namespace std;
int minCandies(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
// Traverse from left to right
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Traverse from right to left
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
// Compute the total number of candies
int totalCandies = 0;
for (int i = 0; i < n; i++) {
totalCandies += candies[i];
}
// Return the total number of candies
return totalCandies;
}
int main() {
vector<int> ratings {1, 0, 2};
int result = minCandies(ratings);
cout << result << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.util.Arrays;
public class Main {
public static int minCandies(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// Traverse from left to right
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Traverse from right to left
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// Compute the total number of candies
int totalCandies = 0;
for (int i = 0; i < n; i++) {
totalCandies += candies[i];
}
// Return the total number of candies
return totalCandies;
}
public static void main(String[] args) {
int[] ratings = {1, 0, 2};
int result = minCandies(ratings);
System.out.println(result);
}
}
def min_candies(arr):
n = len(arr)
dp = [1] * n
# Traverse from left to right
for i in range(1, n):
if arr[i] > arr[i-1]:
dp[i] = dp[i-1] + 1
# Traverse from right to left
for i in range(n-2, -1, -1):
if arr[i] > arr[i+1]:
dp[i] = max(dp[i], dp[i+1] + 1)
# Compute the total number of candies
total_candies = sum(dp)
# Return the total number of candies
return total_candies
# Example input
arr = [1, 0, 2]
# Call the function
result = min_candies(arr)
# Print the result
print(result)
using System;
class GFG
{
static int MinCandies(int[] ratings)
{
int n = ratings.Length;
int[] candies = new int[n];
for (int i = 0; i < n; i++)
{
candies[i] = 1;
}
// Traverse from left to right
for (int i = 1; i < n; i++)
{
if (ratings[i] > ratings[i - 1])
{
candies[i] = candies[i - 1] + 1;
}
}
// Traverse from right to left
for (int i = n - 2; i >= 0; i--)
{
if (ratings[i] > ratings[i + 1])
{
candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
}
}
// Compute the total number of candies
int totalCandies = 0;
for (int i = 0; i < n; i++)
{
totalCandies += candies[i];
}
// Return the total number of candies
return totalCandies;
}
static void Main()
{
int[] ratings = { 1, 0, 2 };
int result = MinCandies(ratings);
Console.WriteLine(result);
}
}
function minCandies(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
// Traverse from left to right
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Traverse from right to left
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// Compute the total number of candies
let totalCandies = 0;
for (let i = 0; i < n; i++) {
totalCandies += candies[i];
}
// Return the total number of candies
return totalCandies;
}
function main() {
const ratings = [1, 0, 2];
const result = minCandies(ratings);
console.log(result);
}
main();
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.
Time Complexity: O(N)
Auxiliary Space: O(N)
Both approaches can solve the candy distribution problem optimally, but the dynamic programming approach has a time and space complexity of O(N), whereas the greedy approach has a time complexity of O(N) and a space complexity of O(1). As a result, if the input size is small, the greedy approach may be preferable, whereas dynamic programming may be required for larger inputs.
Contact Us