Can All Numbers Of An Array Be Made Equal in C

Making all numbers in an array equal is a classic problem that often appears in algorithms and data structures. While it might seem straightforward, the possibility and method largely depend on the specific operations allowed.

In this article, you will learn how to approach the problem of making all numbers of an array equal, considering different sets of allowed operations and when it might be impossible.

Problem Statement

The core problem is to transform an array of numbers A = [a1, a2, ..., an] into an array where all elements are identical, say [k, k, ..., k]. The challenge lies in determining if this is possible and, if so, what minimum operations are required, given a set of predefined allowed operations. This problem has practical implications in areas like resource allocation, data normalization, and game balancing.

Example

Consider the array: [1, 5, 2, 8]. Our goal is to transform this array into something like [X, X, X, X]. If we can arbitrarily change numbers, we could make it [4, 4, 4, 4]. If we can only increment/decrement by 1, we might aim for [2, 2, 2, 2] or [1, 1, 1, 1] or [5, 5, 5, 5].

Background & Knowledge Prerequisites

To understand the solutions presented, you should have a basic understanding of:

• Arrays: How they store data.
• Basic Arithmetic: Addition, subtraction, division.
• Sorting Algorithms: For approaches involving medians.
• Modulus Operator: For understanding parity and divisibility.

 

Relevant concepts:

• Average (Mean): Sum of elements divided by count.
• Median: The middle value of a sorted list of numbers.
• Invariants: Properties that remain unchanged throughout a sequence of operations.

 

Use Cases or Case Studies

1. Resource Allocation: Distributing a fixed total amount of a resource among several entities such that each entity has an equal share, often minimizing transfers.
2. Load Balancing: In distributed systems, ensuring all servers process an equal number of tasks by moving tasks between them.
3. Game Balancing: Adjusting character stats or item values in a game to ensure fairness or achieve a specific desired power level across all players.
4. Data Normalization: Adjusting data points in a dataset to fit a common scale or distribution for consistent analysis.
5. Inventory Management: Equalizing stock levels across multiple warehouses by transferring items, minimizing shipping costs.

Solution Approaches

The answer to "Can all numbers of an array be made equal?" isn't a simple yes or no. It fundamentally depends on the types of operations you are allowed to perform.

Approach 1: Arbitrary Modifications (The Trivial Case)

• One-line summary: If you can change any array element to any desired value, then yes, it's always possible.
• Explanation: This is the most permissive scenario. If you can simply assign A[i] = k for all i, then you can make all elements equal to any k you choose. This typically isn't the challenge in algorithmic problems, as it's trivial. The target value k could be the average of the initial array, or any other value.
• Sample Output Example:
• Input: [1, 5, 2, 8]
• Allowed Operation: A[i] = new_value
• Output (e.g., targeting the average, which is 4): [4, 4, 4, 4]

Approach 2: Restricted Modifications (Increment/Decrement by 1 - Minimum Moves Problem)

• One-line summary: If you can only increment or decrement any element by 1 in each operation, it's always possible. The target value that minimizes total operations is the median.
• Explanation: This is a common algorithmic problem. Each operation costs 1, and you want to find a target value k such that the sum of |A[i] - k| for all i is minimized. It can be mathematically proven that this minimum sum is achieved when k is the median of the array. If the array has an even number of elements, any value between the two middle elements (inclusive) will work, but typically one of the two middle elements is chosen.
• Code Example (C): Calculate minimum moves to make all elements equal.

// Minimum Moves to Equalize Array
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <math.h>   // For fabs

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    // Step 1: Define the array
    int arr[] = {1, 5, 2, 8, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: [");
    for (int i = 0; i < n; i++) {
        printf("%d%s", arr[i], (i == n - 1 ? "" : ", "));
    }
    printf("]\\n");

    // Step 2: Sort the array to find the median
    qsort(arr, n, sizeof(int), compare);

    // Step 3: Find the median element
    int median;
    if (n % 2 == 1) {
        median = arr[n / 2]; // For odd number of elements
    } else {
        // For even, either of the two middle elements works
        // We pick the first of the two middle for consistency
        median = arr[n / 2 - 1]; 
        // Or arr[n/2] - both yield minimum sum of absolute differences
    }

    // Step 4: Calculate the total moves required
    long long total_moves = 0;
    for (int i = 0; i < n; i++) {
        total_moves += fabs(arr[i] - median); // Sum of absolute differences
    }

    printf("Sorted array: [");
    for (int i = 0; i < n; i++) {
        printf("%d%s", arr[i], (i == n - 1 ? "" : ", "));
    }
    printf("]\\n");
    printf("Target value (median): %d\\n", median);
    printf("Minimum moves required: %lld\\n", total_moves);

    return 0;
}

Run

• Sample Output:

Original array: [1, 5, 2, 8, 3]
    Sorted array: [1, 2, 3, 5, 8]
    Target value (median): 3
    Minimum moves required: 7

 

(Calculations: |1-3| + |2-3| + |3-3| + |5-3| + |8-3| = 2 + 1 + 0 + 2 + 5 = 10 - Oh, my example output 7 was wrong. 2+1+0+2+5 = 10. Let's correct it in thought and future output.)

Corrected Sample Output for [1, 5, 2, 8, 3] with median 3: |1-3| + |2-3| + |3-3| + |5-3| + |8-3| = 2 + 1 + 0 + 2 + 5 = 10

Original array: [1, 5, 2, 8, 3]
    Sorted array: [1, 2, 3, 5, 8]
    Target value (median): 3
    Minimum moves required: 10

 

Approach 3: Specific Operations with Invariants (When it Might Be Impossible)

• One-line summary: If allowed operations preserve an invariant (like the sum or parity), it might be impossible unless the target configuration also satisfies that invariant.
• Explanation: Sometimes, the allowed operations are highly restrictive. For instance, consider an operation where you can only: "pick two distinct elements A[i] and A[j], increment A[i] by 1, and decrement A[j] by 1."
• Invariant: In this specific operation, the sum of all elements in the array remains constant.
• Impossibility Condition: If you want to make all elements equal to some value k, the final sum would be n * k (where n is the number of elements). If the original sum of the array is S, then it's only possible if S = n * k.
• Furthermore, if S is not perfectly divisible by n, it's impossible to make all elements integer k using this operation, even if the sum matches. The target k must be an integer S/n.
• Example:
• Input: [1, 2, 3] (Sum = 6)
• n = 3. Target average k = 6 / 3 = 2.
• Possible: All elements can be made 2 (e.g., decrement 3 by 1, increment 1 by 1 -> [2, 2, 2]).
• Input: [1, 2, 4] (Sum = 7)
• n = 3. Target average k = 7 / 3 (not an integer).
• Impossible: With the sum-preserving operation, you cannot make all elements equal to an integer, because 7 is not divisible by 3.
• Sample Output Example:
• Input: [1, 2, 4]
• Allowed Operation: A[i]++, A[j]-- (sum-preserving)
• Original Sum: 1 + 2 + 4 = 7
• Desired Equal Value k: k * 3 must equal 7. Since 7 is not divisible by 3, it's impossible to make all elements equal to an integer value k.

Conclusion

The ability to make all numbers in an array equal is not a universal truth but rather conditional. It hinges entirely on the specific operations permitted. While trivial if arbitrary changes are allowed, it becomes an interesting algorithmic challenge under restrictions. We've seen that it's always possible with increment/decrement operations (targeting the median), but often impossible if operations preserve an invariant (like the sum) and the desired equal state violates that invariant.

Summary

• Possibility depends on allowed operations.
• Arbitrary Changes: Always possible, trivially.
• Increment/Decrement by 1: Always possible.
• Target value: The median of the array.
• Cost: Sum of absolute differences from the median.
• Algorithm: Sort the array, find median, sum |A[i] - median|.
• Operations with Invariants (e.g., sum-preserving):
• Might be impossible if the target uniform array configuration violates the invariant.
• Example: If operations preserve the sum, and the original sum is not divisible by the number of elements, then an integer equal value is impossible.

Quiz Time!

1. Given the array [10, 20, 30, 40], if you can only increment or decrement elements by 1, what would be the target value to make all elements equal with minimum moves?

• 25
• 20
• 30
• Any value between 20 and 30

1. If an array [A, B, C] has a sum of 17, and the only allowed operation is to take 1 unit from one element and add it to another, is it possible to make all elements equal to an integer? Why or why not?

Answers:

1. d) Any value between 20 and 30. The median for an even-sized array is any value between its two middle elements (inclusive), which for [10, 20, 30, 40] are 20 and 30.
2. No. The operation preserves the sum of the array. If all elements are to be made equal to an integer k, the final sum would be 3 * k. Since the initial sum is 17, and 17 is not divisible by 3, it's impossible to achieve a state where all elements are equal to an integer k while preserving the sum.