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
andy
fromnums
. - Choose a bit in
x
and 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
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
class Solution {
public int minNonZeroProduct(int p) {
final int mod = (int) 1e9 + 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;
}
}
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;
}
};
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
}
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);
}