Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A positive value from 4^(d - 1) through 4^d - 1 needs exactly d divisions by four to reach zero. An operation performs one division on each of two selected elements, so count the total individual divisions and pair them as efficiently as possible.

Approach

Define a prefix helper for the total divisions needed by integers from one through x. Walk powers of four and add each block's number of included values times its required division count. For a query [l, r], subtract the helper at l - 1 from the helper at r. Add half this total rounded up to the answer.

The stated ranges contain at least two consecutive integers. The two largest values' required counts differ by at most one, so the largest single-element workload never exceeds the rounded-up half-total. Work can therefore be paired across different elements to attain that bound, using an already-zero element if one final division remains. Sum the independent query answers.

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        n = len(queries)
        res = 0

        def operations(x):
            base = 1
            quats = 1
            ops = 0

            while base <= x:
                ops += (min(base * 4 - 1, x) - base + 1) * (quats)
                quats += 1
                base *= 4

            return ops

        for l, r in queries:
            res += (operations(r) - operations(l - 1) + 1) // 2

        return res

Complexity analysis

Let q = queries.length and R be the largest right endpoint. Time: O(q log R). Auxiliary space: O(1).