You are given a positive integer p. Consider an array nums (1-indexed) that consists of the integers in the inclusive range [1, 2p - 1] in their binary representations. You are allowed to do the following operation any number of times:
x and y from nums.x and swap it with its corresponding bit in y. Corresponding bit refers to the bit that is in the same position in the other integer.For example, if x = 1101 and y = 0011, after swapping the 2nd bit from the right, we have x = 1111 and y = 0001.
Find the minimum non-zero product of nums after performing the above operation any number of times. Return this product modulo 109 + 7.
Note: The answer should be the minimum product before the modulo operation is done.
Example 1:
Input: p = 1 Output: 1 Explanation: nums = [1]. There is only one element, so the product equals that element.
Example 2:
Input: p = 2 Output: 6 Explanation: nums = [01, 10, 11]. Any swap would either make the product 0 or stay the same. Thus, the array product of 1 * 2 * 3 = 6 is already minimized.
Example 3:
Input: p = 3
Output: 1512
Explanation: nums = [001, 010, 011, 100, 101, 110, 111]
- In the first operation we can swap the leftmost bit of the second and fifth elements.
- The resulting array is [001, 110, 011, 100, 001, 110, 111].
- In the second operation we can swap the middle bit of the third and fourth elements.
- The resulting array is [001, 110, 001, 110, 001, 110, 111].
The array product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible product.
Constraints:
1 <= p <= 60For #1969 Minimum Non-Zero Product of the Array Elements, the array contains all integers from 1 to 2^p - 1. The goal is to minimize the non-zero product after performing allowed swaps between bits. Instead of simulating swaps, the key is recognizing a mathematical pattern.
The greedy insight is that the smallest possible product is achieved by pairing values so that most numbers become 2^p - 2, while keeping one maximum value 2^p - 1. This arrangement minimizes the overall product while ensuring it remains non-zero. The final product can be expressed mathematically as (2^p - 1) * (2^p - 2)^(2^(p-1) - 1).
Since the numbers grow very large, the result must be computed using modular exponentiation with modulus 1e9 + 7. Fast power (binary exponentiation), implemented iteratively or recursively, efficiently calculates the exponentiation.
Time Complexity: O(log N) due to fast exponentiation. Space Complexity: O(1) iterative or O(log N) with recursion.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Math + Fast Modular Exponentiation | O(log N) | O(1) iterative / O(log N) recursive |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Try to minimize each element by swapping bits with any of the elements after it.
If you swap out all the 1s in some element, this will lead to a product of zero.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this can appear in coding interviews because they test mathematical reasoning, greedy thinking, and modular exponentiation. These concepts are commonly explored in interviews at large tech companies.
The optimal approach uses a mathematical and greedy observation. Instead of simulating operations, you derive a formula that minimizes the product and compute it using modular exponentiation. This keeps the algorithm efficient even for large p values.
No special data structure is required for this problem. The solution mainly relies on mathematical reasoning and efficient power computation using modular arithmetic.
You should understand greedy reasoning, modular arithmetic, and fast exponentiation (binary power). Recognizing patterns in mathematical expressions is also important for deriving the optimal formula.
The formula involves raising large numbers to very large powers. Modular exponentiation (binary exponentiation) allows computing these powers efficiently under the modulus 1e9+7 without integer overflow.