Minimum Non-Zero Product of the Array Elements solution and explanation
4 more videos on this problem
Leetcode : Minimum Non-Zero Product of the Array ElementsCoding For Dummies · 10:05 · 3K views
1969. Minimum Non-Zero Product of the Array Elements (Leetcode Medium)Programming Live with Larry · 17:27 · 1K views
Minimum non zero product of the array elements.CodeinDepth · 12:31 · 1K views
【每日一题】LeetCode 1969. Minimum Non-Zero Product of the Array Elements, 8/24/2021Huifeng Guan · 25:41 · 392 views
LeetCode 1969: Minimum Non-Zero Product of the Array ElementsAlitaCode · 25:13 · 26 views
The 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
xandyfromnums. - Choose a bit in
xand swap it with its corresponding bit iny. 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
Approach overview
Problem Overview: The array contains every integer from 1 to 2^p - 1. You can swap bits between numbers any number of times. The goal is to produce the smallest possible non-zero product of all elements after performing optimal swaps.
Approach 1: Iterative Product Calculation Using Simulation (O(2^p) time, O(1) space)
A direct way to reason about the result is to simulate how numbers pair together after optimal swaps. The largest number (2^p - 1) stays unchanged because reducing it increases the overall product cost. All other values tend to form pairs that become (2^p - 2) and 1. If you simulate this pattern, you repeatedly multiply the value (2^p - 2) for each pair while keeping one copy of (2^p - 1). This approach mirrors the greedy transformation but computes the product step by step, applying modulo 1e9+7. It works for understanding the structure but becomes infeasible for large p because the array size grows exponentially.
Approach 2: Optimized Mathematical Approach Using Powers (O(log MOD) time, O(1) space)
The key observation is mathematical. After optimal swaps, the minimal configuration keeps one maximum value (2^p - 1), while the remaining numbers form (2^(p-1) - 1) pairs whose effective value becomes (2^p - 2). This leads to a closed-form product: (2^p - 1) * (2^p - 2)^(2^(p-1) - 1). Since the exponent can be extremely large, compute the power using fast modular exponentiation (binary exponentiation). This reduces the exponentiation cost to logarithmic time. The logic relies on insights from math, a greedy observation about pairing values via greedy optimization, and efficient exponentiation that can be implemented recursively or iteratively using ideas from recursion. This is the expected interview solution because it avoids constructing the array entirely.
Recommended for interviews: Interviewers expect the mathematical insight combined with fast exponentiation. Showing the simulation reasoning demonstrates understanding of the pairing pattern, but deriving the formula and computing it in O(log MOD) time shows stronger algorithmic thinking.
Approach 1: Optimized Mathematical Approach Using Powers
This approach reduces the problem to mathematical operations that leverage properties of numbers and their order. We focus on the most significant arrangements to reduce the elements' product by rearranging their bits optimally using the provided conditions.
def min_non_zero_product(p):
MOD = 10**9 + 7
maxNum = (1 << p) - 1
half = maxNum // 2
product = pow(maxNum - 1, half, MOD) * (maxNum % MOD) % MOD
return product
# Example usage
print(min_non_zero_product(1)) # Output: 1
print(min_non_zero_product(2)) # Output: 6
print(min_non_zero_product(3)) # Output: 1512function minNonZeroProduct(p) {
const MOD = 1000000007;
const maxNum = (1 << p) - 1;
const half = Math.floor(maxNum / 2);
const result = BigInt(Math.pow(maxNum - 1, half) % MOD) * BigInt(maxNum);
return Number(result % BigInt(MOD));
}
// Example usage
console.log(minNonZeroProduct(1)); // Output: 1
console.log(minNonZeroProduct(2)); // Output: 6
console.log(minNonZeroProduct(3)); // Output: 1512#include <stdio.h>
#include <math.h>
#define MOD 1000000007
unsigned long long power_mod(unsigned long long base, unsigned long long exp, unsigned long long mod) {
unsigned long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
unsigned long long min_non_zero_product(int p) {
unsigned long long maxNum = (1ULL << p) - 1;
unsigned long long half = maxNum / 2;
unsigned long long prod = (power_mod(maxNum - 1, half, MOD) * (maxNum % MOD)) % MOD;
return prod;
}
int main() {
printf("%llu\n", min_non_zero_product(1)); // Output: 1
printf("%llu\n", min_non_zero_product(2)); // Output: 6
printf("%llu\n", min_non_zero_product(3)); // Output: 1512
return 0;
}In Python, we compute the minimum non-zero product by focusing on the largest number 2^p - 1 and using it in combination with its prior values. We utilize the modulo operation to keep numbers bounded, leveraging Python’s pow function to handle modular exponentiation efficiently.
Time Complexity: O(log(p)) due to the modular exponentiation.
Space Complexity: O(1) as we're using a constant amount of space.
Approach 2: Iterative Product Calculation Using Simulation
This approach simulates the bit manipulation and generates the minimal product iteratively using properties of bit-level operations. The idea is to have systematic element pairings that create complementary binary values to minimize the product effectively.
class Solution {
public int minNonZeroProduct(int p) {
long mod = 1000000007;
long maxNum = (1L << p) - 1;
long pairCount = maxNum / 2;
long result = quickPow(maxNum - 1, pairCount, mod) * (maxNum % mod) % mod;
return (int) result;
}
private long quickPow(long base, long exp, long mod) {
long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = result * base % mod;
}
base = base * base % mod;
exp /= 2;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minNonZeroProduct(1)); // Output: 1
System.out.println(sol.minNonZeroProduct(2)); // Output: 6
System.out.println(sol.minNonZeroProduct(3)); // Output: 1512
}
}public class Solution {
public int MinNonZeroProduct(int p) {
const long MOD = 1000000007;
long maxNum = (1L << p) - 1;
long pairCount = maxNum / 2;
long result = PowerMod(maxNum - 1, pairCount, MOD) * (maxNum % MOD) % MOD;
return (int)result;
}
private long PowerMod(long base, long exp, long mod) {
long result = 1;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinNonZeroProduct(1)); // Output: 1
Console.WriteLine(sol.MinNonZeroProduct(2)); // Output: 6
Console.WriteLine(sol.MinNonZeroProduct(3)); // Output: 1512
}
}The Java solution involves simulating the mathematical deduction using a helper function, quickPow, for efficiently calculating powers under modulo. This replicates the complexity handling from other languages using iterative control structures.
Time Complexity: O(log(p)) due to the power function.
Space Complexity: O(1).
Approach 3: Greedy + Fast Power
We notice that each operation does not change the sum of the elements. When the sum of the elements remains unchanged, to minimize the product, we should maximize the difference between the elements as much as possible.
Since the largest element is 2^p - 1, no matter which element it exchanges with, it will not increase the difference. Therefore, we do not need to consider the case of exchanging with the largest element.
For the other elements in [1,..2^p-2], we pair the first and last elements one by one, that is, pair x with 2^p-1-x. After several operations, each pair of elements becomes (1, 2^p-2). The final product is (2^p-1) times (2^p-2)^{2^{p-1}-1}.
The time complexity is O(p), and the space complexity is O(1).
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;
}
};function minNonZeroProduct(p: number): number {
const mod = BigInt(1e9 + 7);
const qpow = (a: bigint, n: bigint): bigint => {
let ans = BigInt(1);
for (; n; n >>= BigInt(1)) {
if (n & BigInt(1)) {
ans = (ans * a) % mod;
}
a = (a * a) % mod;
}
return ans;
};
const a = (2n ** BigInt(p) - 1n) % mod;
const b = qpow((2n ** BigInt(p) - 2n) % mod, 2n ** (BigInt(p) - 1n) - 1n);
return Number((a * b) % mod);
}func minNonZeroProduct(p int) int {
const mod int = 1e9 + 7
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
a := ((1 << p) - 1) % mod
b := qpow(((1<<p)-2)%mod, (1<<(p-1))-1)
return a * b % mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| Optimized Mathematical Approach Using Powers | Time Complexity: O(log(p)) due to the modular exponentiation. |
| Iterative Product Calculation Using Simulation | Time Complexity: O(log(p)) due to the power function. |
| Greedy + Fast Power | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Product Calculation Using Simulation | O(2^p) | O(1) | Useful for understanding how greedy pair transformations produce the minimal product |
| Optimized Mathematical Approach Using Powers | O(log MOD) | O(1) | Best for production and interviews when p is large |
Frequently asked questions
Is Minimum Non-Zero Product of the Array Elements easy or hard?
The problem is rated Medium on LeetCode but feels harder if you miss the mathematical insight. Once the greedy pairing pattern is recognized, the remaining work is straightforward modular exponentiation.
Minimum Non-Zero Product of the Array Elements Python/Java solution
Implement the mathematical formula and compute the exponent using binary exponentiation. Python often uses a recursive or iterative fast power function, while Java typically implements modular exponentiation using loops and long integers.
How to solve Minimum Non-Zero Product of the Array Elements in O(log n)?
First derive the minimal configuration using greedy pairing: keep one value (2^p − 1) and convert the rest into pairs contributing (2^p − 2). Then compute (2^p − 2)^(2^(p−1) − 1) using fast exponentiation and multiply the result by (2^p − 1) under modulo 1e9+7.
What is the best approach for Minimum Non-Zero Product of the Array Elements?
The optimal solution derives a mathematical formula for the final product: (2^p - 1) * (2^p - 2)^(2^(p-1) - 1). You compute the power using fast modular exponentiation with modulo 1e9+7. This reduces the complexity to O(log MOD) and avoids building the array of size 2^p - 1.
Is Minimum Non-Zero Product of the Array Elements asked at Google/Amazon/Meta?
This problem matches the style of math-heavy algorithm questions sometimes seen at companies like Google and Amazon. It tests mathematical reasoning, modular arithmetic, and fast exponentiation rather than standard data structure manipulation.
What data structure is used in Minimum Non-Zero Product of the Array Elements?
No complex data structure is required. The solution relies mainly on mathematical reasoning, modular arithmetic, and fast exponentiation, typically implemented with simple integer variables.
What is the time complexity of Minimum Non-Zero Product of the Array Elements?
The optimal algorithm runs in O(log MOD) time due to binary exponentiation used for computing large powers under modulo arithmetic. Space complexity is O(1) because only a few numeric variables are stored.