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.

Examples

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

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:
    long long minOperations(std::vector<std::vector<int>>& queries) {
        long long ans = 0;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            long long 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) int64 {
    var ans int64 = 0
    for _, q := range queries {
        l, r := q[0], q[1]
        var cnt int64 = 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
18

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            long 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>): Long {
        var ans = 0L
        for (q in queries) {
            val l = q[0]
            val r = q[1]
            var cnt = 0L
            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
13
14

from typing import List

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>>) -> i64 {
        let mut ans: i64 = 0;
        for q in queries {
            let (l, r) = (q[0], q[1]);
            let mut cnt: i64 = 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: number = 0;
        for (const [l, r] of queries) {
            let cnt: number = 0;
            for (let x = l; x <= r; ++x) {
                let t: number = 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.

Method 2 – Interval Grouping & Logarithmic Counting

Intuition

To reduce a number n to zero by repeated division by 4, we need floor(log₄(n)) + 1 operations. This means we can group numbers by the number of divisions required:

  • Numbers in [1, 3] (i.e., from 4⁰ to 4¹ - 1) require 1 division.
  • Numbers in [4, 15] (i.e., from 4¹ to 4² - 1) require 2 divisions.
  • Numbers in [16, 63] (i.e., from 4² to 4³ - 1) require 3 divisions.
  • … and so on.

This observation allows us to efficiently count the total number of operations needed for any interval.

Approach

  1. For each query [l, r], iterate over division levels d from 1 up to 16 (since 4¹⁶ > 1e9).
  2. For each level, define the interval [prev, cur - 1] where prev = 4^(d-1) and cur = 4^d.
  3. Find the overlap between [l, r] and [prev, cur - 1].
  4. For each overlapping number, add d to the total operations.
  5. After processing all intervals, since each operation can process two numbers, return ceil(total_operations / 2) for the query.
  6. Sum the results for all queries.

Code

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

class Solution {
public:
    long long minOperations(std::vector<std::vector<int>>& queries) {
        long long ans = 0;
        for (auto& q : queries) {
            long long l = q[0], r = q[1], ops = 0;
            long long prev = 1;
            for (int d = 1; d < 17; ++d) {
                long long cur = prev * 4LL;
                long long left = std::max(l, prev), right = std::min(r, cur - 1);
                if (right >= left) ops += (right - left + 1) * d;
                prev = cur;
            }
            ans += (ops + 1) / 2;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func minOperations(queries [][]int) int64 {
    var ans int64 = 0
    for _, q := range queries {
        l, r := int64(q[0]), int64(q[1])
        var ops int64 = 0
        prev := int64(1)
        for d := int64(1); d < 17; d++ {
            cur := prev * 4
            left := max(l, prev)
            right := min(r, cur-1)
            if right >= left {
                ops += (right - left + 1) * d
            }
            prev = cur
        }
        ans += (ops + 1) / 2
    }
    return ans
}
func max(a, b int64) int64 { if a > b { return a }; return b }
func min(a, b int64) int64 { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            long l = q[0], r = q[1], ops = 0;
            long prev = 1;
            for (int d = 1; d < 17; d++) {
                long cur = prev * 4L;
                long left = Math.max(l, prev), right = Math.min(r, cur - 1);
                if (right >= left) ops += (right - left + 1) * d;
                prev = cur;
            }
            ans += (ops + 1) / 2;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun minOperations(queries: Array<IntArray>): Long {
        var ans = 0L
        for (q in queries) {
            var l = q[0].toLong()
            var r = q[1].toLong()
            var ops = 0L
            var prev = 1L
            for (d in 1..16) {
                val cur = prev * 4L
                val left = maxOf(l, prev)
                val right = minOf(r, cur - 1)
                if (right >= left) ops += (right - left + 1) * d
                prev = cur
            }
            ans += (ops + 1) / 2
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from typing import List

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        ans = 0
        for l, r in queries:
            ops = 0
            prev = 1
            for d in range(1, 17):
                cur = prev * 4
                left = max(l, prev)
                right = min(r, cur - 1)
                if right >= left:
                    ops += (right - left + 1) * d
                prev = cur
            ans += (ops + 1) // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn min_operations(queries: Vec<Vec<i32>>) -> i64 {
        let mut ans: i64 = 0;
        for q in queries {
            let l = q[0] as i64;
            let r = q[1] as i64;
            let mut ops: i64 = 0;
            let mut prev: i64 = 1;
            for d in 1..17 {
                let cur = prev * 4;
                let left = std::cmp::max(l, prev);
                let right = std::cmp::min(r, cur - 1);
                if right >= left {
                    ops += (right - left + 1) * d;
                }
                prev = cur;
            }
            ans += (ops + 1) / 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minOperations(queries: number[][]): number {
        let ans: number = 0;
        for (const [l, r] of queries) {
            let ops: number = 0;
            let prev: number = 1;
            for (let d = 1; d < 17; d++) {
                const cur = prev * 4;
                const left = Math.max(l, prev);
                const right = Math.min(r, cur - 1);
                if (right >= left) ops += (right - left + 1) * d;
                prev = cur;
            }
            ans += Math.floor((ops + 1) / 2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(Q * logM) — For each query, we process up to 16 intervals (since 4^16 > 1e9).
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.