Question

1969. Minimum Non-Zero Product of the Array Elements

中文文档

Description

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

Solutions

Solution 1

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);
}