Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1969.html

1969. Minimum Non-Zero Product of the Array Elements

Level

Medium

Description

You are given a positive integer p. Consider an array nums (1-indexed) that consists of the integers in the inclusive range [1, 2^p - 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 10^9 + 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

Solution

The maximum element is 2^p - 1. To make the product minimum, the elements should have the greatest difference possible. That is, for the remaining elements, half of the elements are 1 and half of the elements are 2^p - 2. Then calculate the product.

  • class Solution {
    static final long MODULO = 1000000007;

    public int minNonZeroProduct(int p) {
        long maxNum = (1L << p) - 1;
        long remain = maxNum - 1;
        long pairs = remain / 2;
        long minProduct = quickMul(remain, pairs) * (maxNum % MODULO) % MODULO;
        return (int) (minProduct % MODULO);
    }

    public long quickMul(long x, long n) {
        x %= MODULO;
        long power = 1;
        while (n > 0) {
            if (n % 2 == 1)
                power = power * x % MODULO;
            x = x * x % MODULO;
            n /= 2;
        }
        return power;
    }
}

  • // OJ: https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
// Time: O(logP)
// Space: O(1)
class Solution {
    long long modpow(long long base, long long exp, long long mod) {
        base %= mod;
        long long ans = 1;
        while (exp > 0) {
            if (exp & 1) ans = ans * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return ans;
    }
public:
    int minNonZeroProduct(int p) {
        long long mod = 1e9 + 7, mx = (1LL << p) - 1, next = mx - 1, ans = 1;
        return modpow(next, mx / 2, mod) * (mx % mod) % mod;
    }
};

  • # 1969. Minimum Non-Zero Product of the Array Elements
# https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/

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


  • func minNonZeroProduct(p int) int {
	const mod int = 1e9 + 7
	a := ((1 << p) - 1) % mod
	b := qmi(((1<<p)-2)%mod, (1<<(p-1))-1, mod)
	return a * b % mod
}

func qmi(a, k, p int) int {
	res := 1
	for k != 0 {
		if k&1 == 1 {
			res = res * a % p
		}
		k >>= 1
		a = a * a % p
	}
	return res
}

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

All Problems

All Solutions