Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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] = [lefti, righti]. Each queries[i] represents a query where you have to find the product of all powers[j] with lefti <= j <= righti.
Return an array answers, equal in length to queries, where answers[i] is the answer to the ith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 109 + 7.
Example 1:
Input: n = 15, queries = [[0,1],[2,2],[0,3]] Output: [2,4,64] Explanation: For n = 15, powers = [1,2,4,8]. It can be shown that powers cannot be a smaller size. Answer to 1st query: powers[0] * powers[1] = 1 * 2 = 2. Answer to 2nd query: powers[2] = 4. Answer to 3rd query: powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64. Each answer modulo 109 + 7 yields the same answer, so [2,4,64] is returned.
Example 2:
Input: n = 2, queries = [[0,0]] Output: [2] Explanation: For n = 2, powers = [2]. The answer to the only query is powers[0] = 2. The answer modulo 109 + 7 is the same, so [2] is returned.
Constraints:
1 <= n <= 1091 <= queries.length <= 1050 <= starti <= endi < powers.lengthProblem summary: 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] = [lefti, righti]. Each queries[i] represents a query where you have to find the product of all powers[j] with lefti <= j <= righti. Return an array answers, equal in length to queries, where answers[i] is the answer to the ith query. Since the answer to the ith query may be too large, each answers[i] should be returned modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation
15 [[0,1],[2,2],[0,3]]
2 [[0,0]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2438: Range Product Queries of Powers
class Solution {
public int[] productQueries(int n, int[][] queries) {
int[] powers = new int[Integer.bitCount(n)];
for (int i = 0; n > 0; ++i) {
int x = n & -n;
powers[i] = x;
n -= x;
}
int m = queries.length;
int[] ans = new int[m];
final int mod = (int) 1e9 + 7;
for (int i = 0; i < m; ++i) {
int l = queries[i][0], r = queries[i][1];
long x = 1;
for (int j = l; j <= r; ++j) {
x = x * powers[j] % mod;
}
ans[i] = (int) x;
}
return ans;
}
}
// Accepted solution for LeetCode #2438: Range Product Queries of Powers
func productQueries(n int, queries [][]int) []int {
var powers []int
for n > 0 {
x := n & -n
powers = append(powers, x)
n -= x
}
const mod = 1_000_000_007
ans := make([]int, 0, len(queries))
for _, q := range queries {
l, r := q[0], q[1]
x := 1
for j := l; j <= r; j++ {
x = x * powers[j] % mod
}
ans = append(ans, x)
}
return ans
}
# Accepted solution for LeetCode #2438: Range Product Queries of Powers
class Solution:
def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
powers = []
while n:
x = n & -n
powers.append(x)
n -= x
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)
return ans
// Accepted solution for LeetCode #2438: Range Product Queries of Powers
impl Solution {
pub fn product_queries(mut n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let mut powers = Vec::new();
while n > 0 {
let x = n & -n;
powers.push(x);
n -= x;
}
let modulo = 1_000_000_007;
let mut ans = Vec::with_capacity(queries.len());
for q in queries {
let l = q[0] as usize;
let r = q[1] as usize;
let mut x: i64 = 1;
for j in l..=r {
x = x * powers[j] as i64 % modulo;
}
ans.push(x as i32);
}
ans
}
}
// Accepted solution for LeetCode #2438: Range Product Queries of Powers
function productQueries(n: number, queries: number[][]): number[] {
const powers: number[] = [];
while (n > 0) {
const x = n & -n;
powers.push(x);
n -= x;
}
const mod = 1_000_000_007;
const ans: number[] = [];
for (const [l, r] of queries) {
let x = 1;
for (let j = l; j <= r; j++) {
x = (x * powers[j]) % mod;
}
ans.push(x);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.