# 1. Introduction

This post explores a problem that combines array manipulation with a fairness criterion, known as the "Candy" problem. The goal is to distribute candies to children standing in a line based on their ratings, ensuring that each child gets at least one candy and children with higher ratings receive more candies than their neighbors. This problem is a good exercise in understanding how to apply greedy algorithms for optimal distribution.

## Problem

Given an integer array *ratings*, representing the ratings of *n* children standing in a line, the task is to determine the minimum number of candies needed to distribute to the children. Each child must receive at least one candy, and children with a higher rating should receive more candies than their neighbors.

# 2. Solution Steps

1. Initialize an array *candies* to assign at least one candy to each child.

2. Traverse *ratings* from left to right, incrementing the candy count for a child if their rating is higher than the previous child's rating.

3. Traverse *ratings* from right to left, similarly adjusting the candy count, ensuring children with higher ratings receive more candies than their right neighbor.

4. Sum the values in *candies* to determine the minimum total number of candies required.

# 3. Code Program

```
#include <stdio.h>
#include <stdlib.h>
// Function to find the minimum number of candies required
int candy(int* ratings, int ratingsSize) {
int* candies = (int*) malloc(ratingsSize * sizeof(int));
for (int i = 0; i < ratingsSize; i++) {
candies[i] = 1; // Each child gets at least one candy
}
// Left to right pass
for (int i = 1; i < ratingsSize; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Right to left pass
for (int i = ratingsSize - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}
// Sum up the candies
int totalCandies = 0;
for (int i = 0; i < ratingsSize; i++) {
totalCandies += candies[i];
}
free(candies);
return totalCandies;
}
// Main function to test the candy function
int main() {
int ratings1[] = {1, 0, 2};
printf("Minimum Candies (Example 1): %d\n", candy(ratings1, 3));
int ratings2[] = {1, 2, 2};
printf("Minimum Candies (Example 2): %d\n", candy(ratings2, 3));
return 0;
}
```

### Output:

Minimum Candies (Example 1): 5 Minimum Candies (Example 2): 4

### Explanation:

1. *int* candies = (int*) malloc(ratingsSize * sizeof(int));* - Allocate memory for the candies array.

2. Initialize *candies* array to assign one candy to each child.

**3. First loop**: iterate from left to right, increasing candy count if a child's rating is higher than the previous child.

**4. Second loop**: iterate from right to left, adjusting candy count to satisfy the rule of higher ratings.

5. Sum the total candies required.

6. *free(candies);* - Free the allocated memory for the candies array.

7. The *main* function tests the *candy* function with two examples and prints the minimum number of candies required.

## Comments

## Post a Comment