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:
a and b from the array.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]:
nums = [1, 2].nums[0] and nums[1]. The array becomes [0, 0].For queries[1]:
nums = [2, 3, 4].nums[0] and nums[2]. The array becomes [0, 3, 1].nums[1] and nums[2]. The array becomes [0, 0, 0].The output is 1 + 2 = 3.
Example 2:
Input: queries = [[2,6]]
Output: 4
Explanation:
For queries[0]:
nums = [2, 3, 4, 5, 6].nums[0] and nums[3]. The array becomes [0, 3, 4, 1, 6].nums[2] and nums[4]. The array becomes [0, 3, 1, 1, 1].nums[1] and nums[2]. The array becomes [0, 0, 0, 1, 1].nums[3] and nums[4]. The array becomes [0, 0, 0, 0, 0].The output is 4.
Constraints:
1 <= queries.length <= 105queries[i].length == 2queries[i] == [l, r]1 <= l < r <= 109Problem 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.
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).
| 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 |
Minimum Operations to Make Array Elements Zero | Detailed Deep Dive | Leetcode 3495 | MIK • codestorywithMIK • 10,053 views views
Watch 9 more video solutions →Practice Minimum Operations to Make Array Elements Zero with our built-in code editor and test cases.
Practice on FleetCode