Problem Description

Given a positive integer n, you need to find the minimum number of powers of 2 that sum to n. These powers of 2 form an array called powers, which is sorted in non-decreasing order. There is only one unique way to form this array.

For example, if n = 10 (binary: 1010), then powers = [2, 8] because 10 = 2 + 8 = 2^1 + 2^3.

You are also given a 2D array queries where each queries[i] = [left_i, right_i] represents a query. For each query, you need to find the product of all elements in powers from index left_i to right_i (inclusive).

Your task is to return an array answers where answers[i] is the result of the i-th query. Since the products can be very large, each answer should be returned modulo 10^9 + 7.

The solution works by:

1. Extracting the powers array by repeatedly finding the lowest set bit in n using the operation n & -n, which gives us the smallest power of 2 in the current value of n
2. For each query [l, r], calculating the product powers[l] * powers[l+1] * ... * powers[r] modulo 10^9 + 7

Intuition

To find the minimum number of powers of 2 that sum to n, we need to think about the binary representation of n. Every positive integer can be uniquely represented as a sum of distinct powers of 2 - this is exactly what binary representation tells us! Each bit position that contains a 1 represents a power of 2 that we need.

For example, if n = 13 (binary: 1101), we have 1s at positions 0, 2, and 3, which means 13 = 2^0 + 2^2 + 2^3 = 1 + 4 + 8. This gives us the minimum decomposition automatically because we're using each power of 2 at most once.

The key insight for extracting these powers efficiently is using the bit manipulation trick n & -n. This operation isolates the rightmost (lowest) set bit in n. Why does this work? In two's complement representation, -n flips all bits and adds 1, which has the effect of keeping only the rightmost 1 bit when we AND it with the original number.

Once we extract a power of 2, we subtract it from n and repeat the process until n becomes 0. This naturally gives us the powers in ascending order since we're always extracting the smallest remaining power.

For the query processing part, since we need products of subsequences and the results can be very large, we compute the product iteratively while taking modulo at each step to prevent integer overflow. This is straightforward - we just multiply all elements from index l to r in the powers array.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation consists of two main phases: building the powers array and processing the queries.

Phase 1: Building the Powers Array

We use bit manipulation to extract all powers of 2 from n:

powers = []
while n:
    x = n & -n  # Extract the lowest set bit
    powers.append(x)
    n -= x      # Remove this bit from n

The operation n & -n is the core technique here. It isolates the rightmost set bit by leveraging two's complement arithmetic. For example:

• If n = 10 (binary: 1010), then -n in binary is ...11110110
• n & -n = 1010 & ...11110110 = 0010 = 2
• After subtracting 2, n = 8 (binary: 1000)
• Next iteration: n & -n = 1000 & ...11111000 = 1000 = 8
• After subtracting 8, n = 0, and we're done

This process naturally produces the powers in ascending order since we always extract the smallest remaining power of 2.

Phase 2: Processing Queries

For each query [l, r], we calculate the product of elements from index l to r:

mod = 10**9 + 7
ans = []
for l, r in queries:
    x = 1
    for i in range(l, r + 1):
        x = x * powers[i] % mod
    ans.append(x)

We initialize the product x to 1 and multiply it by each element in the range [l, r]. The modulo operation is applied after each multiplication to prevent integer overflow and keep the numbers manageable.

The time complexity is O(log n) for building the powers array (since n has at most log n bits) and O(q * m) for processing queries, where q is the number of queries and m is the average query range length. The space complexity is O(log n) for storing the powers array.

Example Walkthrough

Let's walk through a complete example with n = 13 and queries = [[0, 2], [1, 2]].

Step 1: Extract the powers array from n = 13

Starting with n = 13 (binary: 1101):

First iteration:

• n = 13 (binary: 1101)
• -n = -13 (binary in two's complement: ...11110011)
• n & -n = 1101 & ...11110011 = 0001 = 1
• Add 1 to powers: powers = [1]
• Update n = 13 - 1 = 12

Second iteration:

• n = 12 (binary: 1100)
• -n = -12 (binary in two's complement: ...11110100)
• n & -n = 1100 & ...11110100 = 0100 = 4
• Add 4 to powers: powers = [1, 4]
• Update n = 12 - 4 = 8

Third iteration:

• n = 8 (binary: 1000)
• -n = -8 (binary in two's complement: ...11111000)
• n & -n = 1000 & ...11111000 = 1000 = 8
• Add 8 to powers: powers = [1, 4, 8]
• Update n = 8 - 8 = 0

The loop ends since n = 0. We have powers = [1, 4, 8].

Step 2: Process the queries

Query 1: [0, 2] - Find product of powers[0] to powers[2]

• Start with x = 1
• Multiply by powers[0] = 1: x = 1 * 1 = 1
• Multiply by powers[1] = 4: x = 1 * 4 = 4
• Multiply by powers[2] = 8: x = 4 * 8 = 32
• Result: 32 % (10^9 + 7) = 32

Query 2: [1, 2] - Find product of powers[1] to powers[2]

• Start with x = 1
• Multiply by powers[1] = 4: x = 1 * 4 = 4
• Multiply by powers[2] = 8: x = 4 * 8 = 32
• Result: 32 % (10^9 + 7) = 32

Final answer: [32, 32]

The key insight is that n & -n efficiently extracts powers of 2 in ascending order, and we can verify: 1 + 4 + 8 = 13 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log n), where m is the length of the queries array and n is the input integer.

• The first while loop extracts all powers of 2 from n using bit manipulation (n & -n gets the rightmost set bit). Since n has at most log n bits, this loop runs O(log n) times.
• For each of the m queries, we iterate through a range [l, r] in the powers array. In the worst case, this range could span all powers, which is at most O(log n) elements.
• Therefore, the total time complexity is O(log n) + O(m × log n) = O(m × log n).

Space Complexity: O(log n) (excluding the space for the answer array).

• The powers array stores the powers of 2 that sum to n. Since n can be represented as a sum of at most log n powers of 2 (corresponding to its set bits), the powers array has at most O(log n) elements.
• The answer array ans has length m, but as mentioned, we exclude this from the space complexity analysis.
• Other variables (x, l, r, mod) use constant space.
• Therefore, the space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo During Multiplication

One of the most common mistakes is computing the entire product first and then applying modulo only at the end:

# WRONG - Can cause integer overflow
product = 1
for i in range(left_index, right_index + 1):
    product *= powers[i]
product %= MOD  # Applied too late!

Why it's problematic: Powers of 2 grow exponentially. For example, if the query range includes multiple large powers like 2^20, 2^21, 2^22, their product becomes astronomical (over 2^63), potentially causing integer overflow even in Python for very large values.

Solution: Apply modulo after each multiplication:

# CORRECT
product = 1
for i in range(left_index, right_index + 1):
    product = (product * powers[i]) % MOD

2. Misunderstanding the Bit Manipulation Logic

Developers might incorrectly try to find powers of 2 using other approaches:

# WRONG - This doesn't give the correct decomposition
powers = []
power = 1
while power <= n:
    if n >= power:
        powers.append(power)
        n -= power
    power *= 2

Why it's problematic: This greedy approach from largest to smallest or sequential checking doesn't guarantee finding the exact powers that sum to n. The bit manipulation n & -n precisely extracts each set bit.

Solution: Stick to the bit manipulation approach:

# CORRECT
while n > 0:
    lowest_bit = n & -n
    powers.append(lowest_bit)
    n -= lowest_bit

3. Off-by-One Errors in Query Processing

It's easy to misinterpret whether the range is inclusive or exclusive:

# WRONG - Excludes the right boundary
for i in range(left_index, right_index):  # Missing right_index!
    product = (product * powers[i]) % MOD

Why it's problematic: The problem specifies that both left_i and right_i are inclusive indices, so we need to include the element at right_index.

Solution: Use range(left_index, right_index + 1):

# CORRECT
for i in range(left_index, right_index + 1):
    product = (product * powers[i]) % MOD

4. Not Handling Edge Cases

Failing to consider edge cases like single-element queries:

# Potential issue if not careful with initialization
if left_index == right_index:
    # Make sure this case is handled correctly
    product = powers[left_index]

Solution: The general loop handles this naturally when initialized properly with product = 1, but it's worth being aware of this case during testing.