Minimum Operations to Make Array Elements Zero

hard array math base-4

Problem

Each query [l, r] defines the array nums = [l, l+1, …, r]. One operation picks two elements a and b and replaces them with floor(a / 4) and floor(b / 4). Find the minimum operations to make every element zero, and return the sum of those minimums over all queries.

A single value x needs cost(x) = floor(log₄ x) + 1 divides to reach 0. If S is the total cost of the whole array, each operation clears 2 units of cost, so the answer for a query is ceil(S / 2) (the largest single cost never dominates because l < r).

Inputqueries = [[1,2],[2,4]]

Output3

[1,2] costs 1+1=2 → ceil(2/2)=1. [2,3,4] costs 1+1+2=4 → ceil(4/2)=2. Total 1+2=3.

queries (l:r, comma-separated)

def minOperations(queries):
    def cost(x):                       # /4 divides to zero one value
        c = 0
        while x > 0:
            x //= 4
            c += 1
        return c
    def g(n):                          # sum of cost(1..n) by base-4 buckets
        if n <= 0:
            return 0
        total, p, k = 0, 1, 0
        while p <= n:
            hi = min(n, p * 4 - 1)     # last value with this cost
            total += (hi - p + 1) * (k + 1)
            p *= 4
            k += 1
        return total
    ans = 0
    for l, r in queries:
        s = g(r) - g(l - 1)            # total cost over [l, r]
        ans += (s + 1) // 2            # each op clears 2 units of cost
    return ans

function minOperations(queries) {
  function cost(x) {                    // /4 divides to zero one value
    let c = 0;
    while (x > 0) { x = Math.floor(x / 4); c++; }
    return c;
  }
  function g(n) {                       // sum of cost(1..n) by base-4 buckets
    if (n <= 0) return 0;
    let total = 0, p = 1, k = 0;
    while (p <= n) {
      const hi = Math.min(n, p * 4 - 1); // last value with this cost
      total += (hi - p + 1) * (k + 1);
      p *= 4;
      k++;
    }
    return total;
  }
  let ans = 0;
  for (const [l, r] of queries) {
    const s = g(r) - g(l - 1);          // total cost over [l, r]
    ans += Math.floor((s + 1) / 2);     // each op clears 2 units of cost
  }
  return ans;
}

long minOperations(int[][] queries) {
    long ans = 0;
    for (int[] q : queries) {
        long s = g(q[1]) - g(q[0] - 1); // total cost over [l, r]
        ans += (s + 1) / 2;             // each op clears 2 units of cost
    }
    return ans;
}
long cost(long x) {                     // /4 divides to zero one value
    long c = 0;
    while (x > 0) { x /= 4; c++; }
    return c;
}
long g(long n) {                        // sum of cost(1..n) by base-4 buckets
    if (n <= 0) return 0;
    long total = 0, p = 1, k = 0;
    while (p <= n) {
        long hi = Math.min(n, p * 4 - 1); // last value with this cost
        total += (hi - p + 1) * (k + 1);
        p *= 4;
        k++;
    }
    return total;
}

long long g(long long n) {               // sum of cost(1..n) by base-4 buckets
    if (n <= 0) return 0;
    long long total = 0, p = 1, k = 0;
    while (p <= n) {
        long long hi = min(n, p * 4 - 1); // last value with this cost
        total += (hi - p + 1) * (k + 1);
        p *= 4;
        k++;
    }
    return total;
}
long long minOperations(vector<vector<int>>& queries) {
    long long ans = 0;
    for (auto& q : queries) {
        long long s = g(q[1]) - g(q[0] - 1); // total cost over [l, r]
        ans += (s + 1) / 2;              // each op clears 2 units of cost
    }
    return ans;
}

Explanation

The array for a query is never built explicitly — it would be far too large (up to 10⁹ values). Instead we reason in terms of cost: cost(x) is how many times you must apply floor(x / 4) before x becomes 0. That equals the number of base-4 digits of x, i.e. floor(log₄ x) + 1.

Every operation touches two values and subtracts one unit of cost from each, so it removes at most 2 units of total cost. If S is the sum of cost(x) over the whole array, then no fewer than ceil(S / 2) operations are possible, and greedily pairing the two most-costly values always achieves that bound — provided the biggest single cost is not larger than the rest combined. Because the range contains at least two distinct numbers (l < r), that condition holds, so the per-query answer is simply ceil(S / 2).

To get S fast we need g(n), the sum of cost(x) for x in 1..n; then S = g(r) − g(l − 1). Values share the same cost in blocks: every x in [4^k, 4^(k+1) − 1] has cost k + 1. We walk those power-of-4 buckets, clip each to n, and add (count) × (k + 1). There are only log₄ n buckets, so each query is handled in logarithmic time.

Finally we accumulate ceil(S / 2) across all queries and return the running total. Using (s + 1) // 2 gives the ceiling with integer arithmetic, and 64-bit integers hold the sum because there can be up to 10⁵ queries.

Example: queries = [[1,2],[2,4]]. For [1,2], costs are 1 and 1, so S = 2 and ceil(2/2) = 1. For [2,4], costs are 1, 1, 2, so S = 4 and ceil(4/2) = 2. The answer is 1 + 2 = 3.

Time: O(Q · log r) Space: O(1)