The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.
| num | Binary Representation | powerful array |
|---|---|---|
| 1 | 00001 | [1] |
| 8 | 01000 | [8] |
| 10 | 01010 | [2, 8] |
| 13 | 01101 | [1, 4, 8] |
| 23 | 10111 | [1, 2, 4, 16] |
The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...].
You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi.
Return an integer array answer such that answer[i] is the answer to the ith query.
Example 1:
Input: queries = [[1,3,7]]
Output: [4]
Explanation:
There is one query.
big_nums[1..3] = [2,1,2]. The product of them is 4. The result is 4 % 7 = 4.
Example 2:
Input: queries = [[2,5,3],[7,7,4]]
Output: [2,2]
Explanation:
There are two queries.
First query: big_nums[2..5] = [1,2,4,1]. The product of them is 8. The result is 8 % 3 = 2.
Second query: big_nums[7] = 2. The result is 2 % 4 = 2.
Constraints:
1 <= queries.length <= 500queries[i].length == 30 <= queries[i][0] <= queries[i][1] <= 10151 <= queries[i][2] <= 105Problem Overview: You are given queries that ask for the product of elements between two indices of a very large conceptual array. The array is not stored explicitly. Instead, its elements are derived from bit contributions of sequential integers. The challenge is computing range products efficiently without ever building the full array.
Approach 1: Dynamic Programming with Bit Contribution Counting (O(q log^2 n) time, O(log n) space)
This method analyzes how many times each power of two appears in the conceptual array prefix. Instead of expanding the big array, you compute prefix statistics using bit manipulation. A helper DP-style routine counts how many set bits appear in ranges of integers and maps those contributions to positions in the big array. For a query [l, r], compute the exponent sum of powers of two in the prefix up to r and subtract the prefix up to l-1. The final product becomes 2^sum % mod. Binary search helps locate which integer contributes to a given index in the conceptual array.
Approach 2: Greedy Bit Decomposition + Binary Search (O(q log n) time, O(1) space)
The optimized strategy treats each element in the big array as a power of two derived from a set bit of some integer. Instead of computing contributions for all numbers, you greedily determine which number contains the k-th bit contribution. Binary search locates the smallest integer whose cumulative set-bit count reaches a target index. Once you know the contributing numbers, extract their bit positions using bit manipulation and accumulate exponent sums. The product over a range becomes modular exponentiation of the total exponent.
Binary search is crucial because the conceptual array length grows quickly as integers contribute multiple set bits. Bit operations like x & (x - 1) or shifting help enumerate or count those bits efficiently. This avoids constructing the array entirely while still answering queries precisely.
Core ideas rely heavily on bit manipulation, prefix counting over implicit structures, and binary search over numeric ranges. Query handling also resembles prefix techniques used in many array problems.
Recommended for interviews: The greedy + binary search solution is the expected optimal approach. It demonstrates that you recognize the array is implicit and can transform the problem into prefix bit counting. Starting with the DP-style counting approach shows understanding of how bit contributions accumulate, but the optimized search-based method shows stronger algorithmic maturity.
Dynamic Programming (DP) is a powerful technique for solving optimization problems. The key idea is to break down the problem into smaller subproblems and solve them just once, storing the results for future reference (usually in an array or matrix). This approach is useful when a problem can be described as a recursion with overlapping subproblems.
For this particular question, consider how you can build up a solution incrementally by solving for smaller cases and using their solutions to construct a solution to the larger case.
This C program uses a simple dynamic programming array to build up the solution. Starting with a base case, it iteratively solves the problem for larger cases using previously computed results, storing them in an array for efficient lookup.
Time Complexity: O(n) - where n is the input size. Each subproblem is computed once.
Space Complexity: O(n) - due to the storage of results in an array.
The greedy algorithm builds up a solution piece by piece by always choosing the next piece that offers the most immediate benefit. It's usually faster because it simplifies the decision-making process, but it can be suboptimal in some cases.
Consider this approach if there's a way to reach the optimal solution by making choices based on the current problem state without needing backtracking or future consideration.
This C solution assumes direct calculation for demonstration purposes. Typically, the greedy choice involves impacting the result based on current state assumptions.
Time Complexity: O(1)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n) - where n is the input size. Each subproblem is computed once. |
| Approach 2: Greedy Method | Time Complexity: O(1) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Bit Contribution Counting | O(q log^2 n) | O(log n) | Useful for understanding how prefix bit counts map to positions in the conceptual array |
| Greedy Bit Decomposition + Binary Search | O(q log n) | O(1) | Best choice for large constraints where the big array cannot be constructed explicitly |
Product of Array Except Self - Leetcode 238 - Python • NeetCode • 747,485 views views
Watch 9 more video solutions →Practice Find Products of Elements of Big Array with our built-in code editor and test cases.
Practice on FleetCode