Minimum Operations to Equalize Array

Difficulty: Easy | Acceptance: 60.40% | Paid: No Topics: Array, Bit Manipulation, Brainteaser

You are given an array nums of n integers. In one operation, you can select any element and flip any single bit in its binary representation. Return the minimum number of operations required to make all elements equal.

• Examples
• Constraints
• Bit-by-Bit Counting
• Brute Force

Examples

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: 
- 1 = 01, 2 = 10, 3 = 11
- For bit 0: 1s=2, 0s=1, min=1
- For bit 1: 1s=2, 0s=1, min=1
- Total = 2

Example 2:

Input: nums = [2,4,8]
Output: 3
Explanation:
- 2 = 0010, 4 = 0100, 8 = 1000
- For bit 0: 1s=0, 0s=3, min=0
- For bit 1: 1s=1, 0s=2, min=1
- For bit 2: 1s=1, 0s=2, min=1
- For bit 3: 1s=1, 0s=2, min=1
- Total = 3

Constraints

- 1 <= n == nums.length <= 100
- 1 <= nums[i] <= 10^5

Bit-by-Bit Counting

Intuition For each bit position, we can independently decide whether to make all bits 0 or all bits 1. The cost for each bit position is the minimum of the count of 1s and the count of 0s.

Steps

• Initialize total operations to 0
• For each bit position from 0 to 30:
  • Count how many numbers have a 1 at that position
  • Add min(count_1s, n - count_1s) to total operations
• Return total operations

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        total_ops = 0
        for bit in range(31):
            count_ones = 0
            for num in nums:
                if (num >> bit) & 1:
                    count_ones += 1
            total_ops += min(count_ones, n - count_ones)
        return total_ops

Complexity

• Time: O(n × 31) = O(n)
• Space: O(1)
• Notes: Optimal solution with linear time complexity.

Brute Force

Intuition Try all possible target values and compute the Hamming distance for each. The minimum Hamming distance is the answer.

Steps

• For each unique value in the array (or all 2³¹ possible values):
  • Compute the Hamming distance between each element and the target
  • Track the minimum total distance
• Return the minimum total distance

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # Only try unique values from the array as potential targets
        unique_targets = set(nums)
        min_ops = float('inf')
        
        for target in unique_targets:
            ops = 0
            for num in nums:
                # Count differing bits
                diff = num ^ target
                ops += bin(diff).count('1')
            min_ops = min(min_ops, ops)
        
        return min_ops

Complexity

• Time: O(n × k) where k is the number of unique values
• Space: O(k) for storing unique values
• Notes: Not optimal for large arrays with many unique values.