C++ Program To Determine Can All Numbers Of An Array Be Made Equal

This article explores a common problem in programming: determining if all numbers in an array can be made equal under specific operational constraints. We will define a clear problem statement and then walk through an efficient C++ solution.

Problem Statement

We are tasked with determining if all numbers within a given integer array can be made equal. The specific constraint for making them equal is that we can only add or subtract an even number from any element. For example, if an element is 5, we can change it to 5 + 2 = 7 or 5 - 4 = 1, but not to 5 + 1 = 6. This implies that the parity (whether a number is even or odd) of any element cannot be changed through these allowed operations. Our goal is to write a C++ program that checks this condition.

Example

Consider these arrays:

• [2, 4, 6]: All numbers are even. They can be made equal (e.g., to 2) by subtracting even numbers. This should return true.
• [1, 3, 5]: All numbers are odd. They can be made equal (e.g., to 1) by subtracting even numbers. This should return true.
• [1, 2, 3]: Contains both odd (1, 3) and even (2) numbers. No matter what even number we add or subtract, an odd number will remain odd, and an even number will remain even. Thus, an odd number can never become equal to an even number. This should return false.

 

Background & Knowledge Prerequisites

To follow along with this article, you should have a basic understanding of:

• C++ Fundamentals: Variables, data types, loops (for loops), conditional statements (if-else).
• Arrays: How to declare, initialize, and iterate through arrays in C++.
• Modular Arithmetic: Specifically, the concept of parity (even or odd numbers) and how the modulo operator (%) can be used to determine it. An even number divided by 2 has a remainder of 0, while an odd number has a remainder of 1.

 

Use Cases or Case Studies

This type of parity-checking problem, while seemingly simple, can be abstracted to various scenarios:

1. Resource Balancing: In a simplified system, if resources can only be moved in "even" batches, this logic applies to check if all agents can reach an equal resource level.
2. Game Mechanics: Certain game rules might only allow "even" point adjustments. This logic could determine if players' scores can ever be synchronized.
3. Data Preprocessing: In numerical algorithms, sometimes data points need to satisfy certain modular properties before further processing. This check could be an initial validation step.
4. Mathematical Puzzles: Many puzzles involving integer transformations rely on invariant properties like parity.

 

Solution Approaches

The key to solving this problem lies in understanding the effect of the allowed operation (adding/subtracting an even number) on the parity of a number.

1. Parity-Based Equality Check

This approach leverages the invariant property of parity under the given operation.

• One-line Summary: If all numbers in the array have the same parity (all even or all odd), they can be made equal; otherwise, they cannot.

• Stepwise Explanation:

1. Handle Edge Cases: If the array is empty or contains only one element, they are trivially "equal," so return true.
2. Determine Reference Parity: Take the first element of the array. Determine its parity (even or odd). This will be our reference parity.
3. Iterate and Compare: Loop through the rest of the elements in the array, starting from the second element.
4. Check Parity: For each element, determine its parity.
5. Mismatched Parity: If any element's parity does not match the reference parity, it's impossible to make all numbers equal. Immediately return false.
6. All Match: If the loop completes without finding any mismatched parities, it means all elements share the same parity. In this case, return true.

• Code Example:

 

// Check if all array numbers can be made equal by even operations
#include <iostream>
#include <vector>
#include <numeric> // Required for std::all_of (optional, for alternative approaches)

// Function to determine if all numbers in an array can be made equal
// by only adding/subtracting even numbers.
bool canAllNumbersBeMadeEqual(const std::vector<int>& arr) {
    // Edge case: An empty array or an array with one element is considered "equal".
    if (arr.size() <= 1) {
        return true;
    }

    // Determine the parity of the first element.
    // 0 for even, 1 for odd.
    int referenceParity = arr[0] % 2;
    if (referenceParity < 0) { // Handle negative numbers correctly for modulo
        referenceParity += 2;
    }

    // Iterate through the rest of the array elements.
    for (size_t i = 1; i < arr.size(); ++i) {
        int currentParity = arr[i] % 2;
        if (currentParity < 0) { // Handle negative numbers correctly for modulo
            currentParity += 2;
        }

        // If any element's parity doesn't match the reference parity,
        // it's impossible to make all numbers equal.
        if (currentParity != referenceParity) {
            return false;
        }
    }

    // If we reached here, all numbers have the same parity.
    return true;
}

int main() {
    // Test Case 1: All even numbers
    std::vector<int> arr1 = {2, 4, 6, 8};
    std::cout << "Array: {2, 4, 6, 8}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr1)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 2: All odd numbers
    std::vector<int> arr2 = {1, 3, 5, 7};
    std::cout << "Array: {1, 3, 5, 7}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr2)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 3: Mixed parities
    std::vector<int> arr3 = {1, 2, 3, 4};
    std::cout << "Array: {1, 2, 3, 4}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr3)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 4: Array with negative numbers
    std::vector<int> arr4 = {-2, -4, 0, -6}; // All even
    std::cout << "Array: {-2, -4, 0, -6}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr4)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 5: Mixed parities with negative numbers
    std::vector<int> arr5 = {-1, 0, 1, 2}; // Mixed
    std::cout << "Array: {-1, 0, 1, 2}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr5)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 6: Single element array
    std::vector<int> arr6 = {42};
    std::cout << "Array: {42}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr6)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // Test Case 7: Empty array
    std::vector<int> arr7 = {};
    std::cout << "Array: {}" << std::endl;
    if (canAllNumbersBeMadeEqual(arr7)) {
        std::cout << "Result: True (All numbers can be made equal)" << std::endl;
    } else {
        std::cout << "Result: False (Numbers cannot be made equal)" << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    return 0;
}

Run

• Sample Output:

Array: {2, 4, 6, 8}
Result: True (All numbers can be made equal)
--------------------
Array: {1, 3, 5, 7}
Result: True (All numbers can be made equal)
--------------------
Array: {1, 2, 3, 4}
Result: False (Numbers cannot be made equal)
--------------------
Array: {-2, -4, 0, -6}
Result: True (All numbers can be made equal)
--------------------
Array: {-1, 0, 1, 2}
Result: False (Numbers cannot be made equal)
--------------------
Array: {42}
Result: True (All numbers can be made equal)
--------------------
Array: {}
Result: True (All numbers can be made equal)
--------------------

 

Conclusion

The problem of determining if all numbers in an array can be made equal by adding or subtracting only even numbers boils down to a simple check of their parity. Since adding or subtracting an even number does not change a number's parity, all elements must initially possess the same parity (all even or all odd) to be potentially made equal. If even a single element has a different parity from the others, equality is impossible under the given constraints.

Summary

• The core problem involves checking if array elements can be made equal by specific operations.
• The allowed operation (add/subtract an even number) preserves the parity of a number.
• For all numbers to be made equal, they must all have the same initial parity (all even or all odd).
• The solution involves determining the parity of the first element and then comparing the parity of all subsequent elements to this reference.
• An efficient C++ implementation iterates through the array once, returning false immediately upon finding a parity mismatch, or true if all parities match.