Python - Solve the Chocolate Distribution Problem Using an Array

Python – Solve the Chocolate Distribution Problem Using an Array

The Chocolate Distribution Problem is a popular coding challenge often asked in DSA interviews. In this problem, you are given an array of integers where each element represents the number of chocolates in a packet. The goal is to distribute these packets among a given number of students such that the difference between the packet with the maximum chocolates and the packet with the minimum chocolates is minimized.

Problem Statement

Given an array arr of size n where each element represents the number of chocolates in a packet, and an integer m representing the number of students, distribute the packets to minimize the difference between the maximum and minimum chocolates given to the students. If it is not possible to distribute the packets (i.e., when m > n), return an appropriate result.

Sample Input and Output

Example 1:

</>

Copy

# Input:
arr = [7, 3, 2, 4, 9, 12, 56]
m = 3

# Output:
Minimum Difference: 2

Example 2:

</>

Copy

# Input:
arr = [7, 3, 2, 4, 9, 12, 56]
m = 4

# Output:
Minimum Difference: 5

Solution Approach

To solve this problem efficiently, follow these steps:

Sort the Array: Sorting the array helps in comparing packets with similar quantities of chocolates.
Use a Sliding Window: Iterate through the sorted array with a window of size m to examine all possible groups of packets.
Calculate the Difference: For each window, compute the difference between the last and first elements (i.e., the maximum and minimum in that group).
Track the Minimum Difference: Update the minimum difference found during the iteration.

Python Program

</>

Copy

def chocolate_distribution(arr, m):
    # If there are no students or no packets, return 0
    if m == 0 or len(arr) == 0:
        return 0
    
    # If the number of students is more than the number of packets, distribution is not possible
    if len(arr) < m:
        return -1

    # Step 1: Sort the array to bring similar values together
    arr.sort()

    # Initialize the minimum difference to a very large number
    min_diff = float('inf')

    # Step 2: Slide through the array with a window of size m
    for i in range(len(arr) - m + 1):
        # Calculate the difference between the maximum and minimum in the current window
        current_diff = arr[i + m - 1] - arr[i]
        if current_diff < min_diff:
            min_diff = current_diff

    return min_diff

# Example 1
arr1 = [7, 3, 2, 4, 9, 12, 56]
m1 = 3
print("Minimum Difference for Example 1:", chocolate_distribution(arr1, m1))

# Example 2
arr2 = [7, 3, 2, 4, 9, 12, 56]
m2 = 4
print("Minimum Difference for Example 2:", chocolate_distribution(arr2, m2))

The program begins by sorting the array, which allows us to easily compare contiguous groups of packets. We then slide a window of size m over the array, calculating the difference between the first and last elements in each window. The minimum of these differences is the answer to the problem.

Conclusion

This tutorial demonstrated how to solve the Chocolate Distribution Problem using an array in Python. By sorting the array and employing a sliding window technique, you can efficiently determine the minimum difference between the packets distributed to students. This approach is a great example of applying basic array manipulation and algorithmic thinking.

TutorialKart

Python – Solve the Chocolate Distribution Problem Using an Array