1969. 数组元素的最小非零乘积

题目描述：

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

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

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

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 10^9 + 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

---

解题分析及思路：

方法：贪心

题解CopyRight：灵茶山艾府 🔗

思路：

例如 x=1000,y=0111 ,如果把 yyy 中最低位以外的 1 全部给 xxx，那么 x′=1110,y′=0001 这样两数乘积最小且非零。

为什么这样做乘积是最小的？

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

记 y = y’ + 2^k 。交换前，两数的乘积为 x ⋅ y = x ⋅ (y′ + 2^k) = x ⋅ y′ + x ⋅ 2^k

交换后，x 变成 x + 2^k ，y 变成 y′ 。两数的乘积为(x + 2^k)⋅y′ = x ⋅ y′ + y′ ⋅ 2^k

对比两个等式可知，满足 x > y′

就可以使交换后的乘积变小。

所以我们不断地将 y 中的 1 与 x 中的 0 交换，就可以将乘积不断减小。由于题目要求乘积不能为 0，我们可以先将 y 减小至 0，然后再寻找一个最低位为 1 的数进行交换，从而让 y 变成 1。

构造

nums包含了 [1,2^p−1] 内的所有整数，我们将这些数分为两组，小于 2^p-1 的为一组，记作 A，其余的为另一组，记作 B。

例如 p = 3 时 A = [1, 2, 3], B = [4, 5, 6, 7]。

B 中除了 2^p − 1 = 7 以外，其余的数均可以和 A 组中的数一一配对，其中配对的两个数之和为 2^p − 1 = 7。

例如 p = 3 时我们有三个数对 (6, 1),(5, 2),(4, 3)，写成二进制为 (110, 001),(101, 010),(100, 011)。

如此构造，数对内没有相同的比特位（一个是 0 另一个必然是 1），我们可以完美地按照上述交换流程交换，交换后的结果为 2^p − 2 = 6 和 1。

交换后，每一对的乘积为 2^p − 2 = 6，这一共有 2^p-1 − 1= 3 对，再乘上不参与配对的 2^p − 1 = 7，得到最小乘积为 7 × 6 × 6 × 6 = 7 × 6³ = 1512（对比一下，交换前的乘积为 7!=5040）。

一般地，最小乘积为 (2^p − 1) ⋅ (2^p − 2)^{2p - 1 − 1}

由于幂次很大，计算时需要用到快速幂，见 50. Pow(x, n)。

注意，由于 2^p-1 − 1 的二进制全是 1，下面写法去掉了快速幂中的 if 判断。

const mod int = 1e9 + 7

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

func pow(x, p int) int {
	res := 1
	for x %= mod; p > 0; p-- {
		res = res * x % mod
		x = x * x % mod
	}
	return res
}

复杂度：

• 时间复杂度：O(N)，其中 N 的值为p
• 空间复杂度：O(1)

执行结果：

• 执行耗时:1 ms,击败了33.33% 的Go用户
• 内存消耗:2 MB,击败了16.67% 的Go用户