## 🧠 Solving LeetCode Until I Become Top 1% — Day `57`

🔹 Problem: Product Queries of Powers of Two

Difficulty: #Medium
Tags: #BitManipulation #PrefixProduct #ModularArithmetic

📝 Problem Summary

We are given:

An integer n which can be expressed as a sum of distinct powers of two (from its binary representation).
Several queries, each [l, r], representing indices in the sorted list of powers-of-two from n.

For each query, compute the product of powers-of-two in that index range, modulo 10^9 + 7.

🧠 My Thought Process

Step 1: Understanding the data structure Every n can be broken into its binary representation, where each 1 corresponds to a power of two that makes up n. Example:

  n = 10 (binary 1010) → powers = [2, 8]

Brute Force Idea:
For each query, loop through the subarray powers[l:r] and multiply the elements, taking modulo each time.
This works because:
- The number of powers is at most 32 (since n ≤ 10^9).
- The queries are applied on a very small list.
Optimized Strategy (not implemented here, but possible):

Precompute prefix products modulo MOD so that each query can be answered in O(1) time instead of O(length of range).

Formula:

  product(l, r) = prefix[r] * inverse(prefix[l-1]) % MOD

where inverse is computed using modular exponentiation.

Algorithm Used: Bit manipulation to extract powers of two + modular multiplication.

⚙️ Code Implementation (Python)

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        powers = []
        i = 0
        # Extract powers of two from n's binary representation
        while (1 << i) <= n:
            if n & (1 << i):
                powers.append(1 << i)
            i += 1

        results = []
        for l, r in queries:
            product = 1
            for j in range(l, r + 1):
                product *= powers[j]
            product %= MOD
            results.append(product)

        return results

⏱️ Time & Space Complexity

Time: O(Q × K)
- Q = number of queries
- K = length of the queried subarray (at most number of set bits in n ≤ 32) → Effectively O(Q) in practice.
Space: O(K) to store the powers.

🧩 Key Takeaways

✅ Using binary representation is a clean way to extract powers-of-two from an integer.
💡 Because the list of powers is tiny (≤ 32), even a brute-force query loop is fast enough.
💭 For larger constraints, prefix products + modular inverses are the way to go.