Medium

题目描述

给你一个正整数 p。考虑一个数组 nums（下标从 1 开始），它包含范围 [1, 2^p - 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]
通过合适的位交换操作，可以得到数组乘积为 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512。

约束条件：

  • 1 <= p <= 60

提示：

  • 尝试通过与之后的元素交换位来最小化每个元素
  • 如果你交换掉某个元素的所有 1，这将导致乘积为零

解题思路

解题思路

这道题的关键在于理解位交换操作的本质和如何构造最小非零乘积。

核心观察：

  1. 数组包含 [1, 2^p - 1] 范围内的所有整数，每个数字都有 p 位二进制表示
  2. 位交换操作不会改变所有数字中 1 的总数，只是重新分配
  3. 要使乘积最小且非零，我们希望尽可能多的数字接近 1，同时避免任何数字变为 0

最优策略分析：

  • 最大的数字是 2^p - 1（所有位都是 1），它无法通过交换变得更小
  • 除了最大数字外，我们可以通过位交换让其他数字尽可能小
  • 最优分配是：让 (2^p - 2)/2 个数字变为 1，(2^p - 2)/2 个数字变为 2^p - 2，保留一个 2^p - 1

数学推导：

  • 总共有 2^p - 1 个数字
  • 最优乘积 = 1^((2^p-2)/2) × (2^p-2)^((2^p-2)/2) × (2^p-1)
  • 化简为 = (2^p-2)^((2^p-2)/2) × (2^p-1)

特殊情况：

  • 当 p = 1 时，只有数字 1，直接返回 1

使用快速幂来计算大数的幂次，并在计算过程中取模避免溢出。

代码实现

class Solution {
public:
    int minNonZeroProduct(int p) {
        const int MOD = 1e9 + 7;
        
        if (p == 1) return 1;
        
        long long base = (1LL << p) - 2;  // 2^p - 2
        long long exp = (base) / 2;       // (2^p - 2) / 2
        long long maxNum = base + 1;      // 2^p - 1
        
        base %= MOD;
        maxNum %= MOD;
        
        return (fastPow(base, exp, MOD) * maxNum) % MOD;
    }
    
private:
    long long fastPow(long long base, long long exp, int mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
};

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        MOD = 10**9 + 7
        
        if p == 1:
            return 1
        
        base = (1 << p) - 2  # 2^p - 2
        exp = base // 2      # (2^p - 2) // 2
        max_num = base + 1   # 2^p - 1
        
        return (pow(base, exp, MOD) * max_num) % MOD

public class Solution {
    public int MinNonZeroProduct(int p) {
        const int MOD = 1000000007;
        
        if (p == 1) return 1;
        
        long baseNum = (1L << p) - 2;  // 2^p - 2
        long exp = baseNum / 2;        // (2^p - 2) / 2
        long maxNum = baseNum + 1;     // 2^p - 1
        
        baseNum %= MOD;
        maxNum %= MOD;
        
        return (int)((FastPow(baseNum, exp, MOD) * maxNum) % MOD);
    }
    
    private long FastPow(long baseNum, long exp, int mod) {
        long result = 1;
        baseNum %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * baseNum) % mod;
            }
            baseNum = (baseNum * baseNum) % mod;
            exp >>= 1;
        }
        return result;
    }
}

var minNonZeroProduct = function(p) {
    const MOD = 1000000007n;
    
    if (p === 1) return 1;
    
    const maxNum = (1n << BigInt(p)) - 1n;
    const pairs = (1n << BigInt(p - 1)) - 1n;
    
    function modPow(base, exp, mod) {
        let result = 1n;
        base = base % mod;
        while (exp > 0n) {
            if (exp % 2n === 1n) {
                result = (result * base) % mod;
            }
            exp = exp >> 1n;
            base = (base * base) % mod;
        }
        return result;
    }
    
    const product = modPow(maxNum - 1n, pairs, MOD);
    return Number((product * (maxNum % MOD)) % MOD);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(p)
空间复杂度O(1)

说明：

  • 时间复杂度：快速幂算法的时间复杂度为 O(log(2^p-2)/2) = O(p)
  • 空间复杂度：只使用了常数额外空间