Minimum Operations to Make Array Elements Zero

Not a bad question!

Since you are given a list of queries, my first instinct was to pre-compute 1e9 values but I was unfortunately hit with a Memory Limit Exceeded; I guess I have to settle for logarithmic time-

My intuition for this question is that we can convert each number in a query into actions. For example:

• the number 4 would take 2 actions as 4 -> 1 -> 0as
• the number 1234 would take 6 actions as 1234 -> 308 -> 77 -> 19 -> 4 -> 1 -> 0

Then, using the newly converted array of actions, we can sum up all the actions inside of any query to get a value; let us call it sum. Using sum, we can calculate the number of operations needed for every query numberOfOperations = sum / 2 + sum % 2 (I tested this out on several test-cases, but it is definitely proveable using induction).

Now, going through the algorithm, we keep track of the minimum operations using ans and iterate through all the queries:

long long ans = 0;
for (vector<int>& query : queries) {
    // more code incoming
}

We first define a function to get the number of actions needed for a given number:

int getActionCount(int number) {
    int counter = 0;
    for (; number > 0; number /= 4) {
        ++counter;
    }
    return counter;
}

Then, we keep track of the current sum of actions using sum and get the left and right action count for the bounds of the query:

long long sum = 0;
int leftActionCount = getActionCount(query[0]);
int rightActionCount = getActionCount(query[1]);

Now, we iterate between the left and right bounds of the query in chunks, where each chunk is separated based on the number's action count, to calculate the sum value for the query:

int currentIndex = query[0];
long long limit = pow(4, leftActionCount);
for (; leftActionCount <= rightActionCount; ++leftActionCount) {
    sum += (min(limit, (long long)query[1]+1)-currentIndex) * leftActionCount;
    currentIndex = limit;
    limit *= 4;
}

Finally, we use the equation above numberOfOperations = sum / 2 + sum % 2 and add it to our ans:

ans += sum / 2 + sum % 2;

code

class Solution {
public:
    long long minOperations(vector<vector<int>>& queries) {
        long long ans = 0;
        for (vector<int>& query : queries) {
            long long sum = 0;
            int leftActionCount = getActionCount(query[0]);
            int rightActionCount = getActionCount(query[1]);

            int currentIndex = query[0];
            long long limit = pow(4, leftActionCount);
            for (; leftActionCount <= rightActionCount; ++leftActionCount) {
                sum += (min(limit, (long long)query[1]+1)-currentIndex) * leftActionCount;
                currentIndex = limit;
                limit *= 4;
            }

            ans += sum / 2 + sum % 2;
        }
        return ans;
    }
private:
    int getActionCount(int number) {
        int counter = 0;
        for (; number > 0; number /= 4) {
            ++counter;
        }
        return counter;
    }
};

complexity

• Time: n(log(R))^2 where n is the number of elements inside queries and R is the largest possible query value.
  • could shrink it down to n(log(R)) if I combine the getPower function for both the left and right side of the interval.
• Space: O(n)

learnings

• i should have known that $\lfloor\log_4 x \rfloor =$ (31-countl_zero(x))/2
  • countl_zero(x) returns the number of consecutive 0 bits in the value of x, starting from the most significant bit

time taken

• 54 minutes and 20 seconds
  • I got distracted setting up my Strava