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

题目描述

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

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

比方说，如果 x = 11_**0**_1 且 y = 00_**1**_1 ，交换右边数起第 2 位后，我们得到 x = 11_**1**_1 和 y = 00_**0**_1 。

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

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

思路

参考官方题解，给定三个整数 $a,b,c$ 且 $a<b<c$，将一个数缩小 1，另一个数增加 1，怎样缩小才能使缩小后的乘积最小？

• 如果缩小最小的元素，即 $(a-1)bc$，缩小了 $bc$；
• 如果缩小最大的元素，即 $ab(c-1)$，缩小了 $ab$。

此时 $ab<bc$，因此缩小最小的元素是最优选。

同理，如果要为另一个数增加 1，增大最大的元素是最优选。

而本题中两个数进行相同的位交换时，本质上就是将一个元素缩小 $2^k$，另一个元素增大 $2^k$。根据上面的推断，我们有一个朴素的贪心思路：优先缩小数组中最小的元素，再增加数组中最大的元素。

对于数组：

$$[1,2,3,\dots ,2^p-2,2^p-1]$$

此时它的乘积为：

$$1\times (10{)}_2\times (11{)}_2\times \cdots \times (11\dots 01{)}_2\times (11\dots 10{)}_2\times (11\dots 11{)}_2$$

我们可以怎样贪心呢？尝试从左向右分析吧。

尝试将第 $i$ 位的所有 1 与第 $2^p-1-i$ 位的 进行交换，我们可以得到：

$$\underset{2^{p-1}-1}{\underbrace{0\times 0\times \dots 0}}\times \underset{2^{p-1}-1}{\underbrace{(11\dots 11{)}_2\cdots \times (11\dots 11{)}_2}}\times (11\dots 11)$$

但是，因为我们要做乘积，因此左侧的 $2^{p-1}-1$ 个数不能为 0，此时就可以将右侧 $2^{p-1}-1$ 个数的最低位与前面的数字交换，最终得到：

$$\underset{2^{p-1}-1}{\underbrace{1\times 1\times \cdots \times 1}}\times \underset{2^{p-1}-1}{\underbrace{(11\dots 10{)}_2\times \cdots \times (11\dots 10{)}_2}}\times (11\dots 11)$$

结果就是 $(2^p-2{)}^{2^{p-1}-1}\times (2^p-1)$。由于幂数较大，可以通过快速幂简化运算。

最简单的 Python 代码为：

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

这份代码的时间复杂度是多少呢？参考这篇回答，pow 和 ** 的时间复杂度都是 $O(\log n)$，因此整体的时间复杂度是 $O(n)$。（好像不大对劲）