原文链接: https://leetcode-cn.com/problems/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.

 

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

中文题目

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：

• 从 nums 中选择两个元素 x 和 y  。
• 选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。

比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。

注意：答案应为取余 之前 的最小值。

 

示例 1：

输入：p = 1
输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。

示例 2：

输入：p = 2
输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。

示例 3：

输入：p = 3
输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中，我们交换第二个和第五个元素最左边的数位。
    - 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
- 第二次操作中，我们交换第三个和第四个元素中间的数位。
    - 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。

 

提示：

• 1 <= p <= 60

通过代码

高赞题解

首先，两个交换的比特必须是不同的，否则交换无影响。

不失一般性，假设 $x$ 参与交换的比特为 $0$，$y$ 参与交换的比特为 $1$，交换的位置为第 $k$ 位。

记 $y=y’+2^k$，则交换前，两数的乘积为

$$
x\cdot y = x\cdot (y’+2^k) = x\cdot y’+x\cdot 2^k
$$

交换后，两数的乘积为

$$
(x+2^k)\cdot (y-2^k) = (x+2^k)\cdot y’ = x\cdot y’+y’\cdot 2^k
$$

对比两个等式可知，要使交换后乘积变小，需要满足

$$
x>y’
$$

这一不等式表明，对于一个数 $y$，如果我们不断地将其二进制中的 $1$ 与另一个满足该不等式的数交换，就可以将乘积不断减小。由于题目要求计算最小非零乘积，我们可以先将 $y$ 减小至 $0$，然后再寻找一个最低位为 $1$ 的数进行交换，从而让 $y$ 变成 $1$。

由于 $\textit{nums}$ 包含了 $[1, 2^p - 1]$ 内的所有整数，我们可以将其分为两组，小于 $2^{p-1}$ 的为一组，记作 $A$，其余的为另一组，记作 $B$。则 $B$ 组中除了 $2^p-1$ 之外，其余的数均可以和 $A$ 组中的数一一配对，要求配对的两个数之和为 $2^p-1$。对于配对的这两个数，若某个数的一个位置是 $1$，则另一个数的该位置上必然是 $0$，因此就可以按照上述交换流程交换，交换后的结果为 $1$ 和 $2^p-2$。

交换后，每一对的乘积为 $2^p-2$，这一共有 $2^{p-1}-1$ 对，再算上不参与配对的 $2^p-1$，得到最小乘积为

$$
(2^p-1)\cdot (2^p-2)^{2^{p-1}-1}
$$

由于幂次很大，计算时需要用到快速幂。不了解的读者可以参考 50. Pow(x, n)。

const mod int = 1e9 + 7

func minNonZeroProduct(p int) int {
	return (1<<p - 1) % mod * pow(1<<p-2, 1<<(p-1)-1) % mod
}

func pow(x, n int) int {
	res := 1
	for x %= mod; n > 0; n >>= 1 {
		res = res * x % mod // 由于 n 的二进制全是 1，所以无需判断 n 的奇偶性
		x = x * x % mod
	}
	return res
}

• 时间复杂度：$O(p)$
• 空间复杂度：$O(1)$

附 $1$：Python 一行解法

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

附 $2$：打表解法

var ans = []int{0, 1, 6, 1512, 581202553, 202795991, 57405498, 316555604, 9253531, 857438053, 586669277, 647824153, 93512543, 391630296, 187678728, 431467833, 539112180, 368376380, 150112795, 484576688, 212293935, 828477683, 106294648, 618323081, 186692306, 513022074, 109245444, 821184946, 2043018, 26450314, 945196305, 138191773, 505517599, 861896614, 640964173, 112322054, 217659727, 680742062, 673217940, 945471045, 554966674, 190830260, 403329489, 305023508, 229675479, 865308368, 689473871, 161536946, 99452142, 720364340, 172386396, 198445540, 265347860, 504260931, 247773741, 65332879, 891336224, 221172799, 643213635, 926891661, 813987236}

func minNonZeroProduct(p int) int {
	return ans[p]
}

统计信息

通过次数	提交次数	AC比率
2980	10598	28.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言