Algorithm

Equal

One day Christy has to distribute some chocolates to her colleagues. She is biased towards her friends and plans to give them more than the others. One of the program managers hears of this and tells her to make sure everyone gets the same number.

To make things difficult, she must equalize the number of chocolates in a series of operations. For each operation, she can give [1,2,5] pieces to all but one colleague. Everyone who gets a piece in a round receives the same number of pieces.

Given a starting distribution, calculate the minimum number of operations needed so that every colleague has the same number of pieces.

Example

arr = [1,1,5]

represents the starting numbers of pieces for each colleague. She can give 2 pieces to the first two and the distribution is then [3,3,5]. On the next round, she gives the same two 2 pieces each, and everyone has the same number: [5,5,5]. Return the number of rounds, 2.

#include <iostream>
#include <vector>
#include <algorithm>

// Function to calculate the number of operations required
// to make a number equal to target using only the operations [1, 2, 5]
int calcOps(int num, int target) {
    int diff = num - target;
    int operations = 0;

    // Adding 5's
    operations += diff / 5;
    diff %= 5;

    // Adding 2's
    operations += diff / 2;
    diff %= 2;

    // Adding 1's
    operations += diff;

    return operations;
}

int findMinOps(std::vector<int>& arr) {
    int minVal = *std::min_element(arr.begin(), arr.end());
    int minOps = INT_MAX;

    // Since we can reduce the minimum value by 1, 2, or 5, 
    // we check for each of these reductions.
    for (int base = 0; base <= 5; base++) {
        int currentOps = 0;

        for (int num : arr) {
            currentOps += calcOps(num, minVal - base);
        }

        minOps = std::min(minOps, currentOps);
    }

    return minOps;
}

int main() {
    std::vector<int> arr = {1, 1, 5};
    int result = findMinOps(arr);
    std::cout << "Minimum operations: " << result << std::endl;
    return 0;
}

Problem Analysis

You need to equalize the chocolates among colleagues using a minimal number of operations. In each operation, you can add chocolates (1, 2, or 5) to all but one colleague.

Key Insight:

Instead of raising all numbers to the highest value, it’s more efficient to reduce them to the smallest value or even slightly below it, due to the operations [1, 2, 5] available.

Solution Approach

  • Identify Potential Targets: Start with the minimum value in the array. Also consider targets that are 1, 2, or 5 units below this minimum.
  • Calculate Operations for Each Target: For each target, calculate how many operations are needed to make all numbers in the array equal to that target.
  • Select Optimal Target: Pick the target that requires the fewest operations.

Code Breakdown

  • calcOps(): Computes the operations to convert a number to a target using [1, 2, 5].
  • findMinOps(): For each potential target (minimum and values slightly below), it calculates the total operations needed and returns the minimum.
  • main(): Initializes the array, invokes findMinOps, and prints the result.

Related Posts