3495. Minimum Operations to Make Array Elements Zero - Solution

The problem

You are given a 2D array queries, where queries[i] is of the form [l, r]. Each queries[i] defines an array of integers nums consisting of elements ranging from l to r, both inclusive.

In one operation, you can:

Select two integers a and b from the array.
Replace them with floor(a / 4) and floor(b / 4).

Your task is to determine the minimum number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.

Example 1:

Input: queries = [[1,2],[2,4]]

Output: 3

Explanation:

For queries[0]:

The initial array is nums = [1, 2].
In the first operation, select nums[0] and nums[1]. The array becomes [0, 0].
The minimum number of operations required is 1.

For queries[1]:

The initial array is nums = [2, 3, 4].
In the first operation, select nums[0] and nums[2]. The array becomes [0, 3, 1].
In the second operation, select nums[1] and nums[2]. The array becomes [0, 0, 0].
The minimum number of operations required is 2.

The output is 1 + 2 = 3.

Example 2:

Input: queries = [[2,6]]

Output: 4

Explanation:

For queries[0]:

The initial array is nums = [2, 3, 4, 5, 6].
In the first operation, select nums[0] and nums[3]. The array becomes [0, 3, 4, 1, 6].
In the second operation, select nums[2] and nums[4]. The array becomes [0, 3, 1, 1, 1].
In the third operation, select nums[1] and nums[2]. The array becomes [0, 0, 0, 1, 1].
In the fourth operation, select nums[3] and nums[4]. The array becomes [0, 0, 0, 0, 0].
The minimum number of operations required is 4.

The output is 4.

Constraints:

1 <= queries.length <= 10⁵
queries[i].length == 2
queries[i] == [l, r]
1 <= l < r <= 10⁹

Approach overview

Problem Overview: You are given an integer array and must compute the minimum number of operations required to turn every element into 0. Each operation effectively removes contributions of specific bits across a contiguous portion of the array. The challenge is recognizing that operations can affect multiple elements at once, which allows grouping work instead of processing each number independently.

Approach 1: Independent Bit Processing (Array + Bit Manipulation) (O(n log M) time, O(1) space)

Each integer can be represented as a set of bits. Instead of reducing numbers directly, treat every bit position independently. For a fixed bit b, scan the array and mark whether that bit is set. Consecutive elements with bit b equal to 1 can be cleared in a single operation applied to that segment. Every time a new segment of 1s begins, you need one operation. Iterate through all bit positions (typically up to 30 for 32‑bit integers) and sum the number of segments. This works because clearing a bit across a continuous range eliminates that bit for all elements in one step.

Approach 2: Prefix Sum Segment Detection (Prefix Sum + Bit Manipulation) (O(n log M) time, O(n) space)

You can formalize the segment counting using a prefix-style scan. Build a running indicator for each bit that tracks whether the current element starts a new active segment. If nums[i] has bit b set but nums[i-1] does not, that index contributes +1 operation for that bit. This behaves similarly to a difference or prefix-sum pattern: detect transitions from 0 → 1 and accumulate them. The prefix scan avoids explicitly storing segments and works in a single pass per bit.

This technique relies heavily on bit manipulation to test individual bits and on prefix-style scans from array traversal. For large values, the algorithm still stays efficient because the number of bits is small (≤ 30). Concepts from math and binary representation make the grouping possible.

Recommended for interviews: The segment-counting solution using bit manipulation and a prefix-style scan is what interviewers expect. It shows you understand how to decompose the problem by bit and exploit contiguous segments. A naive per-element simulation would be far slower and misses the key insight that a single operation can clear the same bit across multiple neighbors.

Solution

According to the problem description, suppose the minimum number of operations required to make an element x become 0 is p, where p is the smallest integer such that 4^p > x.

Once we know the minimum number of operations for each element, for a range [l, r], let s be the sum of the minimum operations for all elements in [l, r], and let mx be the maximum number of operations, which is the number of operations for element r. Then, the minimum number of operations to make all elements in [l, r] become 0 is max(\lceil s / 2 \rceil, mx).

We define a function f(x) to represent the sum of the minimum operations for all elements in the range [1, x]. For each query [l, r], we can compute s = f(r) - f(l - 1) and mx = f(r) - f(r - 1) to obtain the answer.

The time complexity is O(q log M), where q is the number of queries and M is the maximum value in the query range. The space complexity is O(1).

Python

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        def f(x: int) -> int:
            res = 0
            p = i = 1
            while p <= x:
                cnt = min(p * 4 - 1, x) - p + 1
                res += cnt * i
                i += 1
                p *= 4
            return res

        ans = 0
        for l, r in queries:
            s = f(r) - f(l - 1)
            mx = f(r) - f(r - 1)
            ans += max((s + 1) // 2, mx)
        return ans

Java

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            long s = f(r) - f(l - 1);
            long mx = f(r) - f(r - 1);
            ans += Math.max((s + 1) / 2, mx);
        }
        return ans;
    }

    private long f(long x) {
        long res = 0;
        long p = 1;
        int i = 1;
        while (p <= x) {
            long cnt = Math.min(p * 4 - 1, x) - p + 1;
            res += cnt * i;
            i++;
            p *= 4;
        }
        return res;
    }
}

C++

class Solution {
public:
    long long minOperations(vector<vector<int>>& queries) {
        auto f = [&](long long x) {
            long long res = 0;
            long long p = 1;
            int i = 1;
            while (p <= x) {
                long long cnt = min(p * 4 - 1, x) - p + 1;
                res += cnt * i;
                i++;
                p *= 4;
            }
            return res;
        };

        long long ans = 0;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            long long s = f(r) - f(l - 1);
            long long mx = f(r) - f(r - 1);
            ans += max((s + 1) / 2, mx);
        }
        return ans;
    }
};

TypeScript

function minOperations(queries: number[][]): number {
    const f = (x: number): number => {
        let res = 0;
        let p = 1;
        let i = 1;
        while (p <= x) {
            const cnt = Math.min(p * 4 - 1, x) - p + 1;
            res += cnt * i;
            i++;
            p *= 4;
        }
        return res;
    };

    let ans = 0;
    for (const [l, r] of queries) {
        const s = f(r) - f(l - 1);
        const mx = f(r) - f(r - 1);
        ans += Math.max(Math.ceil(s / 2), mx);
    }
    return ans;
}

func minOperations(queries [][]int) (ans int64) {
	f := func(x int64) (res int64) {
		var p int64 = 1
		i := int64(1)
		for p <= x {
			cnt := min(p*4-1, x) - p + 1
			res += cnt * i
			i++
			p *= 4
		}
		return
	}
	for _, q := range queries {
		l, r := int64(q[0]), int64(q[1])
		s := f(r) - f(l-1)
		mx := f(r) - f(r-1)
		ans += max((s+1)/2, mx)
	}
	return
}

Rust

impl Solution {
    pub fn min_operations(queries: Vec<Vec<i32>>) -> i64 {
        let f = |x: i64| -> i64 {
            let mut res: i64 = 0;
            let mut p: i64 = 1;
            let mut i: i64 = 1;
            while p <= x {
                let cnt = std::cmp::min(p * 4 - 1, x) - p + 1;
                res += cnt * i;
                i += 1;
                p *= 4;
            }
            res
        };

        let mut ans: i64 = 0;
        for q in queries {
            let l = q[0] as i64;
            let r = q[1] as i64;
            let s = f(r) - f(l - 1);
            let mx = f(r) - f(r - 1);
            ans += std::cmp::max((s + 1) / 2, mx);
        }
        ans
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Naive Simulation	O(n * value)	O(1)	Conceptual baseline; useful only for understanding the operation mechanics
Bit Segment Counting	O(n log M)	O(1)	General optimal approach when numbers fit within standard integer bit limits
Prefix Sum Transition Scan	O(n log M)	O(n)	When modeling transitions or building reusable prefix arrays for analysis

Frequently asked questions

Is Minimum Operations to Make Array Elements Zero easy or hard?

The problem is rated Hard because the optimal strategy is not obvious from the statement. Many initial attempts simulate operations directly, which becomes inefficient. Recognizing that bits can be processed independently and segments can be cleared together is the key insight.

Minimum Operations to Make Array Elements Zero Python/Java solution

Most implementations iterate over bit positions and scan the array to detect new segments of set bits. The logic is straightforward in Python, Java, C++, Go, or Rust using bitwise AND operations like (num >> b) & 1 to check whether a bit is active.

How to solve Minimum Operations to Make Array Elements Zero in O(n)?

Strict O(n) is not typical unless the value range is treated as a constant. In practice, the algorithm runs in O(n log M) by iterating through each bit position and detecting segment starts using a prefix-style scan. Because the number of bits in integers is small, the runtime behaves close to linear in real scenarios.

What is the best approach for Minimum Operations to Make Array Elements Zero?

The most efficient approach processes each bit position independently and counts contiguous segments where that bit is set. Every segment of 1s requires one operation to clear that bit across the segment. Scanning the array for all bit positions results in O(n log M) time where M is the maximum value in the array.

Is Minimum Operations to Make Array Elements Zero asked at Google/Amazon/Meta?

Problems combining array traversal with bit manipulation and segment counting are common in interviews at companies like Google, Amazon, and Meta. Variants of this question test whether candidates can break numbers into bit contributions and optimize operations across ranges.

What data structure is used in Minimum Operations to Make Array Elements Zero?

The core solution primarily uses arrays and bit manipulation. Some implementations use a prefix-scan or difference-style pattern to detect transitions from 0 to 1 for each bit, but no complex data structures such as heaps or trees are required.

What is the time complexity of Minimum Operations to Make Array Elements Zero?

The optimal solution runs in O(n log M) time, where n is the array length and M is the maximum element value. The algorithm iterates through the array once for each bit position (usually up to 30 bits). Space complexity can be O(1) if segments are counted directly during traversal.

Minimum Operations to Make Array Elements Zero solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Minimum Operations to Make Array Elements Zero solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems