# Minimum Non-Zero Product of the Array Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-non-zero-product-of-the-array-elements
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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:

* Choose two elements `x` and `y` from `nums`.
* Choose a bit in `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 <= 60`

# Approaches
## Greedy Swapping Simulation
This approach simulates the process of swapping bits in a greedy manner. It starts with the initial array of numbers from 1 to `2^p - 1`. It then iteratively searches for any pair of numbers and a bit position where a swap would lead to a smaller overall product. This process is repeated until no such beneficial swap can be found. The final product is then calculated from the resulting array.
**Time:** O(I * (2^p)^2 * p), where `I` is the number of iterations. The size of the array is `N = 2^p - 1`, leading to `O(N^2)` pairs. This complexity is exponential in `p` and thus not feasible. · **Space:** O(2^p) to store the array of numbers.
**Pros:** Conceptually straightforward as it directly models the operations described in the problem.; Guaranteed to find the optimal solution, as the product function is convex in this context.
**Cons:** Extremely inefficient due to multiple nested loops.; The number of iterations required to reach the optimal state can be very large.; Impractical for the given constraints on `p` (up to 60), as it would lead to a timeout.
### Explanation
The core idea is based on the property that for two positive numbers `a` and `b` with a fixed sum `a+b=S`, their product `a*b` is minimized when `a` and `b` are as far apart as possible. A bit swap operation on two numbers `x` and `y` at position `k` changes them to `x'` and `y'`. If `x` has the `k`-th bit as 1 and `y` has it as 0, and we assume `x < y`, swapping this bit results in `x' = x - 2^k` and `y' = y + 2^k`. The new numbers are farther apart, and their product `x'*y'` is smaller than `x*y`. This is because `(x-2^k)(y+2^k) = xy + 2^k(x-y) - (2^k)^2 < xy` since `x-y` is negative.

This greedy strategy involves repeatedly finding such pairs and performing the swap. The process continues until no more such swaps are possible. At this point, for any bit position `k`, all the `1`s for that bit will be concentrated in the largest numbers of the array. While correct in principle, this simulation is computationally very expensive.

```java
// This is a conceptual illustration. A direct implementation would be too slow.
// It would involve a data structure to hold the numbers and loops to find swappable pairs.
public int minNonZeroProductWithGreedy(int p) {
    long n = (1L << p) - 1;
    long[] nums = new long[(int)n];
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }

    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[i] < nums[j]) {
                    long x = nums[i];
                    long y = nums[j];
                    for (int k = 0; k < p; k++) {
                        long bitK = 1L << k;
                        if ((x & bitK) != 0 && (y & bitK) == 0) {
                            nums[i] -= bitK;
                            nums[j] += bitK;
                            changed = true;
                            // Restart or break to handle the modified array
                            // For simplicity, we just show one swap and flag
                        }
                    }
                }
            }
        }
    }

    long MOD = 1_000_000_007;
    long product = 1;
    for (long num : nums) {
        product = (product * (num % MOD)) % MOD;
    }
    return (int)product;
}
```
### Algorithm
- Initialize an array `nums` with integers from `1` to `2^p - 1`.
- Enter a loop that continues as long as improvements can be made to reduce the product.
- Inside the loop, set a flag `improved = false`.
- Iterate through all pairs of indices `(i, j)` in `nums`. Let `x = nums[i]` and `y = nums[j]`.
- To minimize the product, we want to make numbers farther apart. This is achieved by moving a '1' bit from a smaller number to a larger number.
- Assume `x < y`. Iterate through each bit position `k` from `0` to `p-1`.
- If the `k`-th bit of `x` is 1 and the `k`-th bit of `y` is 0, this represents an opportunity to decrease the product.
- Perform the swap: update `nums[i] = x - 2^k` and `nums[j] = y + 2^k`. Set `improved = true`.
- If the `improved` flag is set to `true` during a pass, repeat the process.
- If the loop completes an entire pass over all pairs and bits without any swaps, the array configuration is stable and the product is minimized.
- Calculate the product of all elements in the final `nums` array, taking the result modulo `10^9 + 7` at each multiplication step to prevent overflow.

## Combinatorial Analysis and Fast Modular Exponentiation
This approach leverages a key insight into the structure of the problem. The ability to swap any corresponding bits between any two numbers means we can redistribute all bits at a certain position `i` arbitrarily among the numbers. To minimize the product, we should make the numbers as unequal as possible. This is achieved by constructing as many small numbers (specifically, the value 1) as possible, which forces the remaining numbers to be very large. The final product can be expressed as a formula involving `p`, which can be calculated efficiently using modular exponentiation.
**Time:** O(p). The calculation is dominated by the modular exponentiation `power(base, exp, MOD)`. The exponent `exp` is of the order `2^p`, so its logarithm is `O(p)`. The other `power` calls take `O(log p)`. Thus, the overall time complexity is `O(p)`. · **Space:** O(1), as it only uses a few variables to store intermediate results, regardless of the value of `p`.
**Pros:** Highly efficient with a polynomial time complexity.; Provides a direct, closed-form solution that is easy to implement once the logic is understood.; Scales very well for the given constraints of `p`.
**Cons:** Requires a non-trivial combinatorial insight into the problem's structure.; The derivation of the final array configuration is not immediately obvious.
### Explanation
First, let's analyze the bit counts. The array `nums` contains numbers from `1` to `2^p - 1`. For any bit position `i` from `0` to `p-1`, the number of integers in this range that have the `i`-th bit set to 1 is exactly `2^(p-1)`. The total number of elements is `N = 2^p - 1`. Since we can swap bits freely, we can decide how to distribute the `2^(p-1)` ones and `(2^p - 1) - 2^(p-1) = 2^(p-1) - 1` zeros for each bit position.

To minimize the product `Π x_i` (while keeping `x_i > 0`), we should make the numbers as "spread out" as possible: many small numbers and a few large numbers. The smallest possible non-zero number is 1.

We can construct a maximum of `2^(p-1) - 1` numbers equal to `1`. This is limited by the number of available zeros for bit positions `1` to `p-1`. After forming `2^(p-1) - 1` copies of the number `1`, the remaining bits must be distributed among the remaining `2^(p-1)` numbers. A careful counting of the leftover bits reveals that the remaining numbers will be one copy of `2^p - 1` and `2^(p-1) - 1` copies of `2^p - 2`.

The total product is `1^(...) * (2^p - 2)^(2^(p-1) - 1) * (2^p - 1)^1`. We can compute this efficiently using modular exponentiation to handle the large powers.

```java
class Solution {
    public int minNonZeroProduct(int p) {
        long MOD = 1_000_000_007;

        if (p == 1) {
            return 1;
        }

        // The value of 2^p - 1 modulo MOD. This is the largest number.
        long maxVal = (power(2, p, MOD) - 1 + MOD) % MOD;

        // The value of 2^p - 2 modulo MOD. This is the base for the power.
        long almostMaxVal = (power(2, p, MOD) - 2 + MOD) % MOD;

        // The exponent is 2^(p-1) - 1. Since p <= 60, this fits in a long.
        long count = (1L << (p - 1)) - 1;

        // Calculate (almostMaxVal ^ count) % MOD
        long productOfPairs = power(almostMaxVal, count, MOD);

        // Final result is (maxVal * productOfPairs) % MOD
        long result = (maxVal * productOfPairs) % MOD;

        return (int) result;
    }

    // Helper function for modular exponentiation: (base^exp) % mod
    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- The problem can be solved by determining the final state of the array analytically.
- The key insight is that to minimize the product, we must make the numbers as unequal as possible. This means creating many small numbers (value 1) and a few very large numbers.
- The final array will consist of:
  - One number equal to `2^p - 1`.
  - `2^(p-1) - 1` numbers equal to `2^p - 2`.
  - `2^(p-1) - 1` numbers equal to `1`.
- The product is `(2^p - 1) * (2^p - 2)^(2^(p-1) - 1)`. The `1`s don't affect the product.
- We must compute this value modulo `10^9 + 7`.
- Let `MOD = 10^9 + 7`.
- Calculate `term1 = (2^p - 1) % MOD`.
- Calculate `base = (2^p - 2) % MOD`.
- Calculate the exponent `exp = 2^(p-1) - 1`.
- Use a modular exponentiation function `power(base, exp, MOD)` to compute `term2 = base^exp % MOD`.
- The final result is `(term1 * term2) % MOD`.

# Solutions
### Java

```java
class Solution {
public
  int minNonZeroProduct(int p) {
    final int mod = (int)1 e9 + 7;
    long a = ((1L << p) - 1) % mod;
    long b = qpow(((1L << p) - 2) % mod, (1L << (p - 1)) - 1, mod);
    return (int)(a * b % mod);
  }
private
  long qpow(long a, long n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minNonZeroProduct(int p) {
    using ll = long long;
    const int mod = 1e9 + 7;
    auto qpow = [](ll a, ll n) {
      ll ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return ans;
    };
    ll a = ((1LL << p) - 1) % mod;
    ll b = qpow(((1LL << p) - 2) % mod, (1L << (p - 1)) - 1);
    return a * b % mod;
  }
};

```

### Python

```python
class Solution:
    def minNonZeroProduct(self, p: int) -> int: mod = 10 ** 9 + 7 return (2 ** p - 1) * pow(2 ** p - 2, 2 ** (p - 1) - 1, mod) % mod

```