# Minimum Operations to Make Array Elements Zero
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-make-array-elements-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-elements-zero
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## 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 <= 105`
* `queries[i].length == 2`
* `queries[i] == [l, r]`
* `1 <= l < r <= 109`

# Approaches
## Brute-force Simulation per Query
For each query `[l, r]`, we can simulate the process directly. The core idea is to determine the total number of 'reduction' steps required to make all numbers in the range `[l, r]` zero. A single reduction step is defined as `x -> floor(x / 4)`. The total number of operations is determined by how many of these reduction steps are needed in total across all numbers in the array. Since each operation allows us to perform two such reductions simultaneously (by picking two numbers `a` and `b`), the minimum number of operations will be the total number of reductions divided by two, rounded up.
**Time:** O(sum(r_i - l_i) * log(r_i)) over all queries. Given that `r` can be up to 10^9, the range `r - l` can be very large, making this approach too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store intermediate sums.
**Pros:** Simple to understand and implement.; Directly follows the problem's logic.
**Cons:** Extremely inefficient for large ranges `[l, r]`.; Will result in a Time Limit Exceeded (TLE) error on most platforms for the given constraints.
### Explanation
The algorithm first calculates `ops(x)`, which is the number of reduction steps needed for a single integer `x` to become zero. This is done by repeatedly applying integer division by 4 to `x` and counting the steps until `x` is 0.

For each query `[l, r]`, the algorithm proceeds as follows:

*   Initialize a variable `totalReductions` to zero.
*   Iterate through each integer `x` from `l` to `r`.
*   For each `x`, compute `ops(x)` and add it to `totalReductions`.
*   After the loop, `totalReductions` holds the sum of all reduction steps for the entire array `[l, ..., r]`.
*   The minimum number of operations for the query is `ceil(totalReductions / 2)`, which can be calculated using integer arithmetic as `(totalReductions + 1) / 2`.
*   The results for all queries are summed up to get the final answer.

```java
class Solution {
    private int ops(int n) {
        int count = 0;
        while (n > 0) {
            n /= 4;
            count++;
        }
        return count;
    }

    public long minimumOperations(int[][] queries) {
        long totalOpsSum = 0;
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            long currentTotalReductions = 0;
            // This loop is inefficient for large ranges
            for (int i = l; i <= r; i++) {
                currentTotalReductions += ops(i);
            }
            totalOpsSum += (currentTotalReductions + 1) / 2;
        }
        return totalOpsSum;
    }
}
```
### Algorithm
- For each query `[l, r]`:
  - Initialize `totalReductions = 0`.
  - Loop `x` from `l` to `r`:
    - Calculate `ops(x)`, the number of times `x` must be divided by 4 to become 0.
    - Add `ops(x)` to `totalReductions`.
  - The result for the query is `(totalReductions + 1) / 2`.
- Sum the results for all queries.

## Prefix Sums with Logarithmic Calculation
The brute-force approach is inefficient because it repeatedly calculates sums over large ranges. This can be optimized using prefix sums. We define a function `P(n)` that calculates the total number of reduction steps for all integers from 1 to `n`, i.e., `P(n) = sum_{i=1 to n} ops(i)`. With this function, the total reductions for a range `[l, r]` can be found in constant time as `P(r) - P(l-1)`. The main challenge is to compute `P(n)` efficiently for any given `n` up to 10^9.
**Time:** O(Q * log(max_r)), where `Q` is the number of queries and `max_r` is the maximum value of `r`. This is very efficient and passes the given constraints. · **Space:** O(1), as the prefix sums are calculated on-the-fly without any large data structures.
**Pros:** Highly efficient and scalable for large input ranges.; Optimal time complexity for this problem structure.
**Cons:** The logic is more complex, requiring mathematical insight into the problem structure.; Requires careful handling of large numbers (using `long`) to avoid overflow.
### Explanation
We can compute `P(n)` efficiently by observing that `ops(x)` is constant for all `x` within specific ranges defined by powers of 4.
- `ops(x) = 1` for `x` in `[1, 3]` (i.e., `[4^0, 4^1 - 1]`)
- `ops(x) = 2` for `x` in `[4, 15]` (i.e., `[4^1, 4^2 - 1]`)
- In general, `ops(x) = k` for `x` in `[4^(k-1), 4^k - 1]`

To calculate `P(n)`, we can iterate through these power-of-4 ranges instead of iterating through each number up to `n`.

**Algorithm to calculate `P(n)` (named `calculatePrefixSum`):**

*   Initialize `totalOps = 0`, `k = 1` (ops count), and `powerOf4 = 1`.
*   Loop while `powerOf4 <= n`:
    *   The current range where `ops(x) = k` is `[powerOf4, powerOf4 * 4 - 1]`.
    *   Calculate how many numbers from `[1, n]` fall into this range: `count = min(n, powerOf4 * 4 - 1) - powerOf4 + 1`.
    *   Add the contribution of this group: `totalOps += count * k`.
    *   Update for the next iteration: `powerOf4 *= 4`, `k++`.
*   This loop runs `O(log n)` times, making the calculation very fast.

**Overall Algorithm:**

*   Initialize `totalOpsSum = 0`.
*   For each query `[l, r]`:
    *   Calculate `totalReductions = calculatePrefixSum(r) - calculatePrefixSum(l - 1)`.
    *   The operations for this query are `(totalReductions + 1) / 2`.
    *   Add this to `totalOpsSum`.
*   Return `totalOpsSum`.

```java
class Solution {
    // Calculates sum of ops(i) for i from 1 to n
    private long calculatePrefixSum(long n) {
        if (n == 0) {
            return 0;
        }
        long totalOps = 0;
        long powerOf4 = 1;
        int k = 1;
        while (powerOf4 <= n) {
            long startRange = powerOf4;
            // Use a check to prevent overflow when calculating endRange
            long endRange = (powerOf4 > Long.MAX_VALUE / 4) ? Long.MAX_VALUE : powerOf4 * 4 - 1;
            
            long countInRange = Math.min(n, endRange) - startRange + 1;
            totalOps += countInRange * k;
            
            if (powerOf4 > Long.MAX_VALUE / 4) {
                break; // Avoid overflow in the next iteration
            }
            powerOf4 *= 4;
            k++;
        }
        return totalOps;
    }

    public long minimumOperations(int[][] queries) {
        long totalOpsSum = 0;
        for (int[] query : queries) {
            long l = query[0];
            long r = query[1];
            
            long sum_r = calculatePrefixSum(r);
            long sum_l_minus_1 = calculatePrefixSum(l - 1);
            
            long totalReductions = sum_r - sum_l_minus_1;
            
            totalOpsSum += (totalReductions + 1) / 2;
        }
        return totalOpsSum;
    }
}
```
### Algorithm
- Define a function `calculatePrefixSum(n)` that computes `sum_{i=1 to n} ops(i)` in `O(log n)` time by grouping numbers based on their `ops` value.
- For each query `[l, r]`:
  - Calculate the total reductions for the range: `totalReductions = calculatePrefixSum(r) - calculatePrefixSum(l - 1)`.
  - The result for the query is `(totalReductions + 1) / 2`.
- Sum the results for all queries.