I noted that applying one operation to a number x replaces it with ⌊x/4⌋, so the number of operations needed to turn a single x into 0 is exactly the number of base-4 digits of x, i.e., steps(x) = 1 + ⌊log₄ x⌋ (intervals: 1..3→1, 4..15→2, 16..63→3, …). Since each operation acts on two numbers at once, the minimum operations for an interval [l, r] are constrained by (i) the total step demand S = Σ steps(x) and (ii) the largest per-item demand M = max steps(x). Each operation can reduce the remaining total by at most 2 (one step per chosen item), but a single item still needs at least M operations applied to it across time. Therefore, the optimal number of operations for a query is max(M, ceil(S/2)). Over many queries, I precompute powers of 4 and the prefix sums of steps(x) grouped by [4^{t-1}, 4^t-1] buckets, allowing me to compute S over [l, r] as F(r) − F(l−1) in O(1) per bucket (only up to 15 buckets since 4^15 > 10^9). Finally, I sum max(M, ceil(S/2)) across all queries.
class Solution:
def minOperations(self, queries: List[List[int]]) -> int:
pow4 = [1]
for _ in range(15):
pow4.append(pow4[-1] * 4)
S_full = [0] * (len(pow4))
for t in range(1, len(pow4)):
cnt = pow4[t] - pow4[t-1]
S_full[t] = S_full[t-1] + t * cnt
def steps_of(n: int) -> int:
T = 1
while pow4[T] <= n:
T += 1
return T
def prefix_sum_steps(n: int) -> int:
"""F(n) = sum_{x=1..n} steps(x), n>=0."""
if n <= 0:
return 0
T = 1
while pow4[T] <= n:
T += 1
return S_full[T-1] + T * (n - pow4[T-1] + 1)
total_answer = 0
for l, r in queries:
S = prefix_sum_steps(r) - prefix_sum_steps(l - 1)
M = steps_of(r)
ops = max(M, (S + 1) // 2)
total_answer += ops
return total_answer- Time: O(Q⋅B) where 𝑄 ≤ 10 5 is the number of queries and 𝐵 ≤ 15 is the number of base-4 buckets checked (effectively linear in 𝑄 with a tiny constant)
- Space: 𝑂 ( 𝐵 ) for precomputed tables (constant, since 𝐵 ≤ 15
