1969. Minimum Non-Zero Product of the Array Elements LeetCode Solution
In this guide, you will get 1969. Minimum Non-Zero Product of the Array Elements LeetCode Solution with the best time and space complexity. The solution to Minimum Non-Zero Product of the Array Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Non-Zero Product of the Array Elements
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.
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
Complexity Analysis
Time Complexity: O(\log p)
Space Complexity: O(1)
1969. Minimum Non-Zero Product of the Array Elements LeetCode Solution in C++
class Solution {
public:
int minNonZeroProduct(int p) {
// Can always turn [1..2^p - 1] to [1, 1, ..., 2^p - 2, 2^p - 2, 2^p - 1].
const long n = 1L << p;
const long halfCount = n / 2 - 1;
return modPow(n - 2, halfCount) * ((n - 1) % kMod) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1L;
x %= kMod;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x, n / 2) % kMod;
}
}; /* code provided by PROGIEZ */
1969. Minimum Non-Zero Product of the Array Elements LeetCode Solution in Java
class Solution {
public int minNonZeroProduct(int p) {
// Can always turn [1..2^p - 1] to [1, 1, ..., 2^p - 2, 2^p - 2, 2^p - 1].
final long n = 1L << p;
final long halfCount = n / 2 - 1;
return (int) (modPow(n - 2, halfCount) * ((n - 1) % kMod) % kMod);
}
private static final int kMod = 1_000_000_007;
private long modPow(long x, long n) {
if (n == 0)
return 1L;
x %= kMod;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x, n / 2) % kMod;
}
} // code provided by PROGIEZ
1969. Minimum Non-Zero Product of the Array Elements LeetCode Solution in Python
class Solution:
def minNonZeroProduct(self, p: int) -> int:
kMod = 1_000_000_007
# Can always turn [1..2^p - 1] to [1, 1, ..., 2^p - 2, 2^p - 2, 2^p - 1].
n = 1 << p
halfCount = n // 2 - 1
return pow(n - 2, halfCount, kMod) * ((n - 1) % kMod) % kMod # code by PROGIEZ
