Skip to content

3674. Minimum Operations to Equalize Array

SourceWeekly Contest 466 Q1DifficultyEasyRating1369

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

Thinking

One operation replaces a subarray by its \(\gcd\). If every entry is already equal, no operation is needed; otherwise one operation on the whole array equalizes it.

The answer is therefore \(0\) or \(1\). A scan that looks for a value different from the first element decides which.

\(n\le 100\) is a 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