Minimum Operations to Make Array Elements Zero

Minimum Operations to Make Array Elements Zero - Problem

You are given a 2D array queries, where queries[i] is of the form [l, r]. Each queries[i] defines an array of integers nums consisting of elements ranging from l to r, both inclusive.

In one operation, you can:

Select two integers a and b from the array.
Replace them with floor(a / 4) and floor(b / 4).

Your task is to determine the minimum number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.

Input & Output

Example 1 — Basic Range

$ Input: queries = [[1,3]]

› Output: 3

💡 Note: Range [1,3]: 1 needs 1 op (1→0), 2 needs 1 op (2→0), 3 needs 1 op (3→0). Total: 1+1+1 = 3.

Example 2 — Larger Numbers

$ Input: queries = [[5,7]]

› Output: 6

💡 Note: Range [5,7]: 5→1→0 (2 ops), 6→1→0 (2 ops), 7→1→0 (2 ops). Total: 2+2+2 = 6

Example 3 — Multiple Queries

$ Input: queries = [[1,2],[3,4]]

› Output: 5

💡 Note: Query [1,2]: 1→0 (1 op), 2→0 (1 op). Sum=2. Query [3,4]: 3→0 (1 op), 4→1→0 (2 ops). Sum=3. Total: 2+3 = 5.

Constraints

1 ≤ queries.length ≤ 10⁵
1 ≤ l ≤ r ≤ 10⁶

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 10

The key insight is that each number n requires exactly ⌊log₄(n)⌋ + 1 operations to reach zero through repeated division by 4. The optimal approach uses precomputation with prefix sums to answer queries in O(1) time. Time: O(M + n), Space: O(M) where M is the maximum value and n is the number of queries.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(n × m × log m)	O(m)	Simulate the division process for each number until it reaches zero
Mathematical Formula	O(n × m)	O(1)	Calculate operations directly using logarithmic formula
Precomputed Operations	O(M + n)	O(M)	Precompute operations for all possible values to handle multiple queries efficiently

Simulation Approach — Algorithm Steps

Generate array from l to r for each query
For each number, repeatedly divide by 4 until zero
Count operations and sum results

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Range

Create array [l, l+1, ..., r]

Simulate Operations

For each number, divide by 4 until zero

Count Total

Sum all operations across queries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int operationsNeeded(int num) {
    int ops = 0;
    while (num > 0) {
        num /= 4;
        ops++;
    }
    return ops;
}

int solution(int queries[][2], int queryCount) {
    int totalSum = 0;
    
    for (int i = 0; i < queryCount; i++) {
        int l = queries[i][0], r = queries[i][1];
        int querySum = 0;
        
        for (int num = l; num <= r; num++) {
            querySum += operationsNeeded(num);
        }
        
        totalSum += querySum;
    }
    
    return totalSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int queries[1000][2];
    int queryCount = 0;
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int l = 0, r = 0;
            sscanf(ptr, "%d,%d", &l, &r);
            queries[queryCount][0] = l;
            queries[queryCount][1] = r;
            queryCount++;
            
            // Skip to next [
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr) ptr++; // Skip ]
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(queries, queryCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × log m)

n queries × m numbers per range × log₄(max_value) operations per number

⚡ Linearithmic

Space Complexity

O(m)

Store array of size m for largest range

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler