Minimum Non-Zero Product of the Array Elements — Solution
Minimum Non-Zero Product of the Array Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Non-Zero Product of the Array Elements is a medium coding problem on math, greedy and recursion, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Greedy, Recursion
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Start with the array nums holding every integer from 1 to 2^p - 1, each written in binary with p bits.
An operation picks two elements x and y and a bit position, and swaps the bits of x and y at that position. You may perform any number of operations.
Return the smallest positive product of all the elements that can be reached. Minimise the actual product first, then return it modulo 10^9 + 7.
Example 1
Input: p = 1
Output: 1
Explanation: nums = [1]; nothing can change.
Example 2
Input: p = 2
Output: 6
Explanation: nums = [01, 10, 11]; no swap gives a smaller non-zero product than 1·2·3.
Example 3
Input: p = 3
Output: 1512
Explanation: Turn [001..111] into [1, 6, 1, 6, 1, 6, 7]: 7 · 6³ = 1512.
Constraints
1 <= p <= 60
Hints for Minimum Non-Zero Product of the Array Elements
Hint 1
Swapping bits never changes the total number of 1s in each bit position, so the sum of the array is fixed — and a fixed sum gives the smallest product when values are as uneven as possible.
Hint 2
Pair
xwith2^p - 1 - x: their bits are complementary, so swaps can turn the pair into1and2^p - 2(zero would make the product 0, which is not allowed).Hint 3
That leaves
2^p - 1alone and2^(p-1) - 1pairs, each contributing2^p - 2: the answer is(2^p - 1) · (2^p - 2)^(2^(p-1) - 1).
How to solve Minimum Non-Zero Product of the Array Elements
Push every pair of complementary numbers to the extremes 1 and 2^p - 2. The minimum product is (2^p - 1) · (2^p - 2)^(2^(p-1) - 1), computed with modular exponentiation.
Approach
- Let
top = 2^p - 1(reduced modulo M = 10^9 + 7 for the multiplication) andbase = (2^p - 2) mod M. - The exponent
2^(p-1) - 1isp - 1one-bits in binary, so the power equalsbase^(2^0) · base^(2^1) · … · base^(2^(p-2)): start withresult = 1, cur = baseand repeatp - 1timesresult *= cur; cur *= cur(all modulo M). - Return
top · result mod M.
Why it works
Within a pair x, 2^p - 1 - x the two numbers have opposite bits everywhere, so every 1-bit except the lowest can be swapped into one of them, leaving 1 and 2^p - 2. For two positive numbers with a fixed sum s, a·(s - a) is smallest when a is as small as possible, so each pair contributes at least 1·(2^p - 2) — and no element may become 0. The unpaired maximum 2^p - 1 cannot be reduced without creating a zero elsewhere. Writing the exponent as a run of ones avoids ever storing 2^(p-1) - 1, which is too large for exact arithmetic in some languages.
Complexity
- Time —
O(p) - Space —
O(1)
Pitfalls
- Reduce
2^p - 2modulo M before multiplying; with p = 60 the raw value is 10^18. - Do not reduce the exponent modulo M — exponents follow Fermat's rule (mod M - 1), not the value's modulus. The repeated-squaring loop sidesteps it entirely.
- p = 1 has no pairs: the loop runs zero times and the answer is 1.
Reference solution
Python
def minNonZeroProduct(p: int) -> int:
MOD = 10 ** 9 + 7
top = (1 << p) - 1
return top % MOD * pow(top - 1, (1 << (p - 1)) - 1, MOD) % MODJava
public static int minNonZeroProduct(int p) {
final long MOD = 1000000007L;
long pow2 = 1;
for (int i = 0; i < p; i++) pow2 = pow2 * 2 % MOD;
long top = (pow2 - 1 + MOD) % MOD;
long cur = (pow2 - 2 + MOD) % MOD;
long result = 1;
for (int i = 0; i < p - 1; i++) {
result = result * cur % MOD;
cur = cur * cur % MOD;
}
return (int) (top * result % MOD);
}C++
int minNonZeroProduct(int p) {
const long long MOD = 1000000007LL;
long long pow2 = 1;
for (int i = 0; i < p; i++) pow2 = pow2 * 2 % MOD;
long long top = (pow2 - 1 + MOD) % MOD;
long long cur = (pow2 - 2 + MOD) % MOD;
long long result = 1;
for (int i = 0; i < p - 1; i++) {
result = result * cur % MOD;
cur = cur * cur % MOD;
}
return (int) (top * result % MOD);
}JavaScript
var minNonZeroProduct = function(p) {
var MOD = 1000000007;
var mulMod = function(a, b) {
var hi = Math.floor(b / 65536), lo = b % 65536;
return ((a * hi) % MOD * 65536 + a * lo) % MOD;
};
var pow2 = 1;
for (var i = 0; i < p; i++) pow2 = pow2 * 2 % MOD;
var top = (pow2 - 1 + MOD) % MOD;
var cur = (pow2 - 2 + MOD) % MOD;
var result = 1;
for (i = 0; i < p - 1; i++) {
result = mulMod(result, cur);
cur = mulMod(cur, cur);
}
return mulMod(top, result);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms · Recursion