Minimum Non-Zero Product of the Array Elements

Medium
1314.

Minimum Non-Zero Product of the Array Elements

Minimum Non-Zero Product of the Array Elements is a medium coding problem on math, greedy and recursion, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} p
 * @return {number}
 */
var minNonZeroProduct = function(p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. 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.

  2. Hint 2

    Pair x with 2^p - 1 - x: their bits are complementary, so swaps can turn the pair into 1 and 2^p - 2 (zero would make the product 0, which is not allowed).

  3. Hint 3

    That leaves 2^p - 1 alone and 2^(p-1) - 1 pairs, each contributing 2^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

  1. Let top = 2^p - 1 (reduced modulo M = 10^9 + 7 for the multiplication) and base = (2^p - 2) mod M.
  2. The exponent 2^(p-1) - 1 is p - 1 one-bits in binary, so the power equals base^(2^0) · base^(2^1) · … · base^(2^(p-2)): start with result = 1, cur = base and repeat p - 1 times result *= cur; cur *= cur (all modulo M).
  3. 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 - 2 modulo 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) % MOD

Java

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