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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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^5
  • queries[i].length == 2
  • queries[i] == [l, r]
  • 1 <= l < r <= 10^9

Examples

Solution

Method 1 – Greedy & Bit Manipulation

Intuition

Each operation reduces two numbers by dividing them by 4 (floor). The process is similar to reducing the largest numbers first, and the minimum number of operations is determined by the maximum number of times you need to divide any number in the range by 4 until it reaches zero. Since you can pair up numbers, the answer for each query is the ceiling of half the sum of the number of divisions needed for each number.

Approach

  1. For each query [l, r], count the number of times each number in [l, r] needs to be divided by 4 to reach zero.
  2. For each number x in [l, r], count the number of times you can divide x by 4 before it becomes zero.
  3. Sum up all these counts for the range.
  4. Since each operation can process two numbers, the minimum number of operations is ceil(total_count / 2).
  5. For large ranges, use math to compute the sum efficiently by counting how many numbers have a given number of divisions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minOperations(vector<vector<int>>& queries) {
        int ans = 0;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            int cnt = 0;
            for (int x = l; x <= r; ++x) {
                int t = x;
                while (t) {
                    t /= 4;
                    ++cnt;
                }
            }
            ans += (cnt + 1) / 2;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func minOperations(queries [][]int) int {
    ans := 0
    for _, q := range queries {
        l, r := q[0], q[1]
        cnt := 0
        for x := l; x <= r; x++ {
            t := x
            for t > 0 {
                t /= 4
                cnt++
            }
        }
        ans += (cnt + 1) / 2
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minOperations(int[][] queries) {
        int ans = 0;
        for (int[] q : queries) {
            int l = q[0], r = q[1], cnt = 0;
            for (int x = l; x <= r; ++x) {
                int t = x;
                while (t > 0) {
                    t /= 4;
                    cnt++;
                }
            }
            ans += (cnt + 1) / 2;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minOperations(queries: Array<IntArray>): Int {
        var ans = 0
        for (q in queries) {
            val l = q[0]
            val r = q[1]
            var cnt = 0
            for (x in l..r) {
                var t = x
                while (t > 0) {
                    t /= 4
                    cnt++
                }
            }
            ans += (cnt + 1) / 2
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minOperations(self, queries: list[list[int]]) -> int:
        ans: int = 0
        for l, r in queries:
            cnt: int = 0
            for x in range(l, r + 1):
                t: int = x
                while t:
                    t //= 4
                    cnt += 1
            ans += (cnt + 1) // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn min_operations(queries: Vec<Vec<i32>>) -> i32 {
        let mut ans = 0;
        for q in queries {
            let (l, r) = (q[0], q[1]);
            let mut cnt = 0;
            for x in l..=r {
                let mut t = x;
                while t > 0 {
                    t /= 4;
                    cnt += 1;
                }
            }
            ans += (cnt + 1) / 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minOperations(queries: number[][]): number {
        let ans = 0;
        for (const [l, r] of queries) {
            let cnt = 0;
            for (let x = l; x <= r; ++x) {
                let t = x;
                while (t > 0) {
                    t = Math.floor(t / 4);
                    cnt++;
                }
            }
            ans += Math.floor((cnt + 1) / 2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(Q * N * logM) — For each query, for each number in the range, we divide by 4 until zero. Q = number of queries, N = range size, M = max number value.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.