Minimum Non-Zero Product of the Array Elements — Editorial

Opening the reading…

Intuitionthe swaps rearrange bits, not the number of 1s in each column

There are 2^p - 1 values, containing every nonzero p-bit pattern exactly once. In every bit position, exactly half of the 2^p possible patterns contain a 1, so nums contains exactly 2^(p - 1) ones in that column. Swapping corresponding bits between two elements can move those ones between rows, but it cannot change their total in any column.

A positive product becomes smaller when an element becomes smaller, so the best arrangement packs as many rows as possible into the smallest positive value, 1. Each 1-valued row uses one 1 from every bit column, so at most 2^(p - 1) - 1 rows can become 1 while still leaving enough bits to keep every other row nonzero. The remaining bits force one row to be 2^p - 1 and the other 2^(p - 1) - 1 rows to be 2^p - 2.

The column-wise bit counts determine the three groups in the optimal arrangement.

Approachturn the arrangement into one modular power

Handle p = 1 directly, because the array contains only 1 and the product is already 1; this also avoids relying on a special interpretation of 0 raised to the power 0.

Set maxVal to 2^p - 1 using a 64-bit shift, because the largest value must keep every bit set and an int shift can overflow before the subtraction.

Set base to maxVal - 1 and exponent to 2^(p - 1) - 1, because the optimal arrangement has exponent copies of 2^p - 2 and one copy of 2^p - 1.

Compute maxVal multiplied by base raised to exponent modulo 10^9 + 7, because multiplication modulo the prime can be applied after every factor without changing the final remainder.

Use binary exponentiation: multiply the answer by the current base when the current exponent bit is 1, square the base, and discard that bit by halving the exponent; this reduces the number of multiplications from exponential in p to linear in p.

Return the modular result as an int after every intermediate product has been reduced, because the requested answer is the minimum product's remainder rather than the enormous product itself.

Complexitythe exponent has only p binary digits

MEASURE	BOUND	WHY
Time	O(p)	Binary exponentiation processes one bit of the exponent per loop iteration. The exponent is 2^(p - 1) - 1, whose binary representation has p - 1 bits, so no factor is processed more than once. In the worst permitted input, p is 60 and the loop still has only 60 iterations.
Space	O(1)	The computation stores only a constant number of 64-bit values, and the output integer is excluded because it is required output rather than working memory. The bound does not degrade with the input shape; p changes the values, not the number of stored variables.

Here p is the input bit width, and MOD is the fixed value 10^9 + 7.

Annotated solutionC++ · modular arithmetic with binary exponentiation

CPPConstruct the forced factors and evaluate the repeated factor with binary exponentiation.

#include <cstdint>

using namespace std;

class Solution {
public:
    int minNonZeroProduct(int p) {
        const long long MOD = 1000000007LL;
        if (p == 1) {
            return 1;
        }

        long long maxVal = (1LL << p) - 1;
        long long base = maxVal - 1;
        long long exponent = (1LL << (p - 1)) - 1;

        long long result = (maxVal % MOD) * modPow(base, exponent, MOD) % MOD;
        return static_cast<int>(result);
    }

private:
    long long modPow(long long base, long long exponent, long long mod) {
        long long result = 1;

        while (exponent > 0) {
            if (exponent & 1LL) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent >>= 1;
        }

        return result;
    }
};

The important distinction is between the true product and its modular representation. The arrangement is determined before any modulo operation: one maxVal factor and exponent copies of base. Only after that structure is known do you reduce each multiplication modulo MOD. Because both stored factors are below MOD, their product fits safely in a signed 64-bit value before the remainder is taken.