Candy - C Solution

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.