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

【LetMeFly】1969.数组元素的最小非零乘积：贪心(快速幂)

力扣题目链接：https://leetcode.cn/problems/minimum-non-zero-product-of-the-array-elements/

给你一个正整数 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

方法一：贪心(快速幂)

方法

解决这道题需要明白两点：

1. 尽量把所有数变成111...10和000...01的形式；
2. 如何使用快速幂快速计算。

原因

为什么要尽量变成111...10和000...01的形式？

题目中的两个数x = 1100和y = 0011，x * y = 1100 * 0010 + 1100 * 0001。

我们看从左往右的第三个1，它的“贡献”是1100 * 0010。

而如果交换第三个1的位置使得x = 1110且y = 0001（x * y = 1000 * 0001 + 0100 * 0001 + 0010 * 0001），

则第三个1的“贡献”是0010 * 0001。

有没有发现，第三个1不论在x中还是在y中，其对x * y的贡献中总有“0010乘以另一个数”这一部分。

那么能不能让另一个数尽可能小？可以。因最终结果要“非零”，因此另一个数最小为1。

能变成多少个111...10和000...01的形式？

从1到2^p-1的二进制数中，除了2^p-1（二进制下全部为1）外，其余数（偶数个）正好可以两两配对（使得每一位上总计1个1和1个0）。

因此最终可以变成$2^p-1$乘以：$\frac{2^p-2}{2}$个$2^p-2$

快速幂是什么？

快速幂用于快速计算$a^b\mod p$的结果，其原理是将b看成二进制数。

例如$a^6=a^{110_{(2)}}=a^{100_{(2)}}\times a^{10_{(2)}}$，而$a^{100_{(2)}}$又可以通过$a^{10_{(2)}}\times a$得到。

这样便将$O(b)$的时间复杂度将为了$b$二进制长度的复杂度$O(\log b)$

具体可参考快速幂小解。

时空复杂度

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

AC代码

C++

typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
private:
    ll Pow(ll a, ll b) {
        a %= MOD;
        ll ans = 1;
        while (b) {
            if (b & 1) {
                ans = ans * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return ans;
    }
public:
    // (2 ^ p - 1) * ((2 ^ p - 2) ^ ((2 ^ p - 2) / 2))
    int minNonZeroProduct(int p) {
        return (((1LL << p) - 1) % MOD) * Pow((1LL << p) - 2, ((1LL << p) - 2) / 2) % MOD;
    }
};

Python

MOD = int(1e9) + 7

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        return ((1 << p) - 1) * pow((1 << p) - 2, ((1 << p) - 2) // 2, MOD) % MOD  # 记得是//而不是/

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136872322