Skip to content

3674. Minimum Operations to Equalize Array

Description

You are given an integer array nums of length n.

In one operation, choose any subarray nums[l...r] (0 <= l <= r < n) and replace each element in that subarray with the bitwise AND of all elements.

Return the minimum number of operations required to make all elements of nums equal.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,2]

Output: 1

Explanation:

Choose nums[0...1]: (1 AND 2) = 0, so the array becomes [0, 0] and all elements are equal in 1 operation.

Example 2:

Input: nums = [5,5,5]

Output: 0

Explanation:

nums is [5, 5, 5] which already has all elements equal, so 0 operations are required.

 

Constraints:

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 105

Solutions

Solution 1: Single Pass

If all elements in \(\textit{nums}\) are equal, no operations are needed; otherwise, we can select the entire array as a subarray and perform one operation.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return int(any(x != nums[0] for x in nums))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int minOperations(int[] nums) {
        for (int x : nums) {
            if (x != nums[0]) {
                return 1;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minOperations(vector<int>& nums) {
        for (int x : nums) {
            if (x != nums[0]) {
                return 1;
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
func minOperations(nums []int) int {
    for _, x := range nums {
        if x != nums[0] {
            return 1
        }
    }
    return 0
}

1
2
3
4
5
6
7
8
function minOperations(nums: number[]): number {
    for (const x of nums) {
        if (x !== nums[0]) {
            return 1;
        }
    }
    return 0;
}

Comments