Range Product Queries of Powers - Practice Coding Problems

Range Product Queries of Powers - Problem

Given a positive integer n, there exists a 0-indexed array called powers, composed of the minimum number of powers of 2 that sum to n. The array is sorted in non-decreasing order, and there is only one way to form the array.

You are also given a 0-indexed 2D integer array queries, where queries[i] = [left_i, right_i]. Each queries[i] represents a query where you have to find the product of all powers[j] with left_i ≤ j ≤ right_i.

Return an array answers, equal in length to queries, where answers[i] is the answer to the i^th query. Since the answer to the i^th query may be too large, each answers[i] should be returned modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 15, queries = [[0,1],[2,2]]

› Output: [2,4]

💡 Note: 15 = 8+4+2+1, so powers = [1,2,4,8]. Query [0,1]: 1×2=2. Query [2,2]: 4.

Example 2 — Single Element

$ Input: n = 2, queries = [[0,0]]

› Output: [2]

💡 Note: 2 = 2¹, so powers = [2]. Query [0,0]: 2.

Example 3 — Large Range

$ Input: n = 31, queries = [[0,4]]

› Output: [248]

💡 Note: 31 = 16+8+4+2+1, so powers = [1,2,4,8,16]. Query [0,4]: 1×2×4×8×16=1024, but 1024 mod (10⁹+7) = 1024.

Constraints

1 ≤ n ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
0 ≤ left_i ≤ right_i < popcount(n)

Visualization

Tap to expand

Understanding the Visualization

Input

n = 15, queries = [[0,1],[2,2]]

Process

Convert to powers array [1,2,4,8] and calculate range products

Output

Return [2,4] with modulo applied

Key Takeaway

🎯 Key Insight: Convert products to sums of exponents, then use prefix sums for O(1) range queries

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is that products of powers of 2 can be calculated as 2^(sum of exponents). The optimal approach uses prefix sums to compute range exponent sums in O(1) time per query. Time: O(log n + q log MOD), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(log n + q log MOD)	O(log n)	Use prefix sums of exponents to calculate range products efficiently
Brute Force	O(q × k)	O(log n)	Generate powers array and calculate product for each query directly

Prefix Sum Optimization — Algorithm Steps

Step 1: Extract exponents from powers of 2
Step 2: Build prefix sum array of exponents
Step 3: Use prefix sums to get range exponent sum and calculate 2^sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Exponents

Get exponents [0,1,2,3] from powers [1,2,4,8]

Build Prefix Sum

Create cumulative sum array

Range Query

Use prefix sums to get exponent sum, then 2^sum

Code -

solution.c — C

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

long long powerMod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int* solution(int n, int** queries, int queriesSize, int* returnSize) {
    const int MOD = 1000000007;
    
    // Extract exponents from binary representation
    int exponents[64];
    int exponentCount = 0;
    int bitPos = 0;
    while (n > 0) {
        if (n & 1) {
            exponents[exponentCount++] = bitPos;
        }
        n >>= 1;
        bitPos++;
    }
    
    // Build prefix sum array
    int prefix[65];
    prefix[0] = 0;
    for (int i = 0; i < exponentCount; i++) {
        prefix[i + 1] = prefix[i] + exponents[i];
    }
    
    int* answers = malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int left = queries[i][0], right = queries[i][1];
        int exponentSum = prefix[right + 1] - prefix[left];
        int product = (int)powerMod(2, exponentSum, MOD);
        answers[i] = product;
    }
    
    return answers;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for demo
    int queriesSize = 2;
    int** queries = malloc(queriesSize * sizeof(int*));
    queries[0] = malloc(2 * sizeof(int));
    queries[1] = malloc(2 * sizeof(int));
    queries[0][0] = 0; queries[0][1] = 1;
    queries[1][0] = 2; queries[1][1] = 2;
    
    int returnSize;
    int* result = solution(n, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n + q log MOD)

Build powers array O(log n), then q queries with O(log MOD) modular exponentiation each

⚡ Linearithmic

Space Complexity

O(log n)

Prefix sum array stores at most log n exponents

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~25 min Avg. Time

487 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

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler