Distribute Candy

Name: Merge Overlapping Intervals
Brand: LogicMojo
SKU: .
Availability: InStock
Rating: 4.8 (230 reviews)

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Distribute Candy
Greedy Approach

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.

To address the problem, follow the instructions below:

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] and the value of ans[i + 1] is at least ans[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 at least ans[i + 1], then update the value of ans[i + 1] as ans[i] + 1.
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.
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.