Facebook Pixel

3674. Minimum Operations to Equalize Array

EasyBit ManipulationBrainteaserArray
LeetCode ↗

Problem Description

You are given an integer array nums of length n.

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

Your task is to 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.

Key observations about the problem:

  • The bitwise AND operation can only keep bits the same or turn them off — it never turns bits on. So applying an operation can only make values smaller or keep them unchanged.
  • If every element in nums is already the same, the answer is 0 since no operation is needed.
  • If the elements are not all equal, a single operation on the entire array replaces every element with the AND of all elements, instantly making them all equal. Hence the answer is at most 1.

Therefore, the answer is simply 0 when all elements are equal, and 1 otherwise — which is exactly what the one-liner checks:

int(any(x != nums[0] for x in nums))

This expression evaluates to 1 if any element differs from the first element, and 0 if all elements match.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Graph?noDirecttransformationoryesSimulation /Basic DSA

The AND operation applied to the whole array equalizes all elements in one step; the problem reduces to checking whether any element differs from the first, requiring at most one operation.

Open in Flowchart

Intuition

The first thing to notice is what the operation actually does: replacing a subarray with the bitwise AND of its elements. The AND operation has a crucial property — it can only turn bits off, never on. This means values can only stay the same or decrease; we can never "raise" an element back up.

Now think about the two possible states of the array:

  • All elements are already equal. There is nothing to do, so the answer is 0.
  • At least one element differs. Can we finish in just one move? Yes — pick the entire array as the subarray. One operation replaces every element with the AND of all elements, and now everything is equal by definition. So one operation always suffices.

Could the answer ever be more than 1? No, because the single whole-array operation works for any input. Could it ever be less than 1 when elements differ? No, because at least one operation is needed to change anything.

So the problem, despite its appearance, collapses to a simple equality check:

  • Answer is 0 if all elements match the first element.
  • Answer is 1 otherwise.

This is exactly what the expression int(any(x != nums[0] for x in nums)) computes — any(...) detects whether some element differs from nums[0], and int(...) converts that boolean into the required 0 or 1.

The key insight is recognizing that the freedom to choose any subarray — including the whole array — makes the problem trivial: the operation is powerful enough to solve everything in a single step.

Solution Approach

any(x != nums[0] for x in nums)


- `any(...)` returns `True` as soon as it finds the first mismatch (short-circuiting, so it may stop early).
- It returns `False` only after confirming every element equals `nums[0]`.

3. **Convert the result to the answer.** The boolean maps directly to the operation count:
- `False` (all equal) → `0` operations.
- `True` (some difference) → `1` operation (apply the AND over the entire array `nums[0...n-1]`).

Wrapping with `int(...)` performs this conversion, since `int(False) == 0` and `int(True) == 1`.

**Full implementation:**

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

Example Walkthrough

Let's trace through the approach with two small examples.

Example 1: nums = [1, 5, 3]

We scan the array and compare every element against nums[0] = 1:

IndexValueCompare with nums[0] = 1Result
011 != 1False
155 != 1True — mismatch found!

The moment any(...) sees 5 != 1, it short-circuits and returns True (index 2 is never even checked). Wrapping with int(...) gives the answer 1.

Why is 1 correct? Apply a single operation on the entire array nums[0...2]:

1 AND 5 AND 3
= 0b001 AND 0b101 AND 0b011
= 0b001
= 1

After the operation, the array becomes [1, 1, 1] — all elements equal in exactly one operation. Since the elements were not all equal initially, at least one operation was required, so 1 is optimal.

Example 2: nums = [7, 7, 7]

Again compare every element against nums[0] = 7:

IndexValueCompare with nums[0] = 7Result
077 != 7False
177 != 7False
277 != 7False

No mismatch is ever found, so any(...) returns False, and int(False) yields 0. The array is already uniform — no operation is needed.

Takeaway: the walkthrough confirms the core insight — the answer can only ever be 0 (already equal) or 1 (one whole-array AND fixes everything), and the one-liner int(any(x != nums[0] for x in nums)) distinguishes precisely between these two cases in O(n) time and O(1) space.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minOperations(self, nums: List[int]) -> int:
6        # Check whether any element differs from the first element.
7        # - If all elements are equal, no operation is needed -> return 0.
8        # - If at least one element differs, a single operation suffices -> return 1.
9        # any(...) returns a boolean, and int(...) converts it to 0 or 1.
10        return int(any(num != nums[0] for num in nums))
11
1class Solution {
2    /**
3     * Determines the minimum number of operations needed.
4     *
5     * Logic:
6     * - If all elements in the array are identical, no operation is needed (return 0).
7     * - Otherwise, exactly one operation is sufficient (return 1).
8     *
9     * @param nums the input array of integers
10     * @return the minimum number of operations (0 or 1)
11     */
12    public int minOperations(int[] nums) {
13        // Iterate through every element in the array
14        for (int num : nums) {
15            // If any element differs from the first element,
16            // the array is not uniform, so one operation is required
17            if (num != nums[0]) {
18                return 1;
19            }
20        }
21        // All elements are identical; no operation is needed
22        return 0;
23    }
24}
25
1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        // Iterate through every element in the array
5        for (int num : nums) {
6            // If any element differs from the first element,
7            // the array is not uniform, so one operation is needed
8            if (num != nums[0]) {
9                return 1;
10            }
11        }
12        // All elements are identical, so no operation is required
13        return 0;
14    }
15};
16```
17
18**Explanation of the logic:**
19
201. **Check uniformity**: The loop compares each element `num` against the first element `nums[0]`.
212. **Early exit**: As soon as a mismatch is found, the function returns `1`, meaning at least one operation is necessary.
223. **Default case**: If the loop completes without finding any difference, all elements are equal, and `0` is returned.
23
24**Alternative perspectives:**
25
26- **Using STL algorithms**: The same logic can be expressed more concisely with `std::all_of` or `std::adjacent_find`:
27
28```cpp
29class Solution {
30public:
31    int minOperations(vector<int>& nums) {
32        // Return 0 if all elements equal the first one, otherwise 1
33        return all_of(nums.begin(), nums.end(),
34                      [&](int num) { return num == nums[0]; }) ? 0 : 1;
35    }
36};
37
1/**
2 * Determines the minimum number of operations needed.
3 * If all elements in the array are identical, no operation is needed (returns 0).
4 * Otherwise, a single operation is sufficient (returns 1).
5 *
6 * @param nums - The input array of numbers
7 * @returns The minimum number of operations (0 or 1)
8 */
9function minOperations(nums: number[]): number {
10    // Iterate through each element in the array
11    for (const num of nums) {
12        // If any element differs from the first element,
13        // the array is not uniform, so one operation is required
14        if (num !== nums[0]) {
15            return 1;
16        }
17    }
18    // All elements are identical, so no operation is needed
19    return 0;
20}
21```
22
23**Explanation of the logic:**
24
251. **Iteration**: The function loops through every element of `nums`.
262. **Comparison**: Each element is compared against the first element `nums[0]`.
273. **Early exit**: As soon as a mismatch is found, the function returns `1`, since at least one operation is needed to make the array uniform.
284. **Uniform case**: If the loop completes without finding any mismatch, all elements are equal, so the function returns `0`.
29
30**Complexity analysis:**
31
32- **Time complexity**: O(n) — in the worst case, every element is checked once.
33- **Space complexity**: O(1) — only constant extra space is used.
34
35**Alternative approach** using built-in array methods:
36
37```typescript
38/**
39 * Alternative one-liner using Array.prototype.every.
40 * Returns 0 if all elements equal the first element, otherwise 1.
41 *
42 * @param nums - The input array of numbers
43 * @returns The minimum number of operations (0 or 1)
44 */
45function minOperations(nums: number[]): number {
46    // Check whether every element matches the first one
47    return nums.every((num) => num === nums[0]) ? 0 : 1;
48}
49

Time and Space Complexity

  • Time complexity: O(n), where n is the length of the array nums. The expression any(x != nums[0] for x in nums) iterates through the array, comparing each element x with nums[0]. In the worst case (e.g., when all elements are equal), every element must be checked, resulting in n comparisons.

  • Space complexity: O(1). The generator expression (x != nums[0] for x in nums) evaluates elements lazily one at a time without building an intermediate list, so only a constant amount of extra space is used.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overcomplicating the Problem with Simulation or DP

The most frequent mistake is treating this as a complex optimization problem — trying to simulate operations, enumerate subarray choices, or build a dynamic programming solution to "search" for the minimum number of operations.

Why it happens: The operation description (choose any subarray, replace with AND) looks like it invites combinatorial exploration. Solvers jump into coding before analyzing the structural properties of the AND operation.

Why it's wrong: A single operation over the entire array nums[0...n-1] already makes every element equal. The answer can therefore never exceed 1, and any simulation/DP is wasted effort that risks TLE on large inputs.

Fix: Reason about the operation first. Since AND over the whole array equalizes everything in one step, the only question left is: are the elements already equal? That reduces the problem to a single linear scan.

2. Forgetting the Zero-Operation Case

A tempting "shortcut" is to always return 1:

# Wrong: ignores arrays that are already uniform
def minOperations(self, nums: List[int]) -> int:
    return 1

This fails on inputs like [5, 5, 5] or any single-element array [7], where the correct answer is 0 because no operation is needed. Always check uniformity before concluding an operation is required:

# Correct
return int(any(x != nums[0] for x in nums))

3. Assuming the Final Value Must Be Zero

Some solvers assume the array must be reduced until all elements become 0, then count how many AND operations that takes (e.g., counting distinct values or bit levels).

Why it's wrong: The goal is only that all elements be equal — the common value can be anything. The AND of the whole array (which may be nonzero) is a perfectly valid final value reached in one operation. For example, [6, 7] becomes [6, 6] in one step; there is no need to drive it to [0, 0].

4. Inefficient Equality Check

Checking uniformity with len(set(nums)) > 1 works but always builds a full set in O(n) extra space, even when the first two elements already differ. The generator-based any(x != nums[0] for x in nums) short-circuits on the first mismatch and uses O(1) space — a small but meaningful distinction when n is large.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which data structure is used to implement priority queue?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More