3495: Minimum-Operations-to-Make-Array-Elements-Zero
Hard

table of contents

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:

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

learnings

time taken