class Solution {
public:
int minNonZeroProduct(int p) {
}
};
1969. 数组元素的最小非零乘积
给你一个正整数 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原站题解
php 解法, 执行用时: 8 ms, 内存消耗: 19.8 MB, 提交时间: 2024-03-20 09:26:30
class Solution {
const MOD = 1000000007;
private function pow($x, $p) {
$x %= self::MOD;
$res = 1;
while ($p-- > 0) {
$res = ($res * $x) % self::MOD;
$x = ($x * $x) % self::MOD;
}
return $res;
}
/**
* @param Integer $p
* @return Integer
*/
public function minNonZeroProduct($p) {
$k = pow(2, $p) - 1;
$k %= self::MOD;
return (int)($k * $this->pow($k - 1, $p - 1) % self::MOD);
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-03-20 09:23:37
impl Solution {
pub fn min_non_zero_product(p: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
fn pow(mut x: i64, p: i32) -> i64 {
x %= MOD;
let mut res = 1;
for _ in 0..p {
res = res * x % MOD;
x = x * x % MOD;
}
res
}
let k = (1 << p) - 1;
(k % MOD * pow(k - 1, p - 1) % MOD) as _
}
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 49.1 MB, 提交时间: 2024-03-20 09:23:10
const MOD = 1_000_000_007n;
function pow(x, p) {
let res = 1n;
while (p--) {
res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
/**
* @param {number} p
* @return {number}
*/
var minNonZeroProduct = function(p) {
const k = (1n << BigInt(p)) - 1n;
return k * pow(k - 1n, p - 1) % MOD;
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.2 MB, 提交时间: 2024-03-20 09:22:27
public class Solution {
private static final int MOD = 1_000_000_007;
private long pow(long x, int p) {
x %= MOD;
long res = 1;
while (p-- > 0) {
res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
public int minNonZeroProduct(int p) {
long k = (1L << p) - 1;
return (int) (k % MOD * pow(k - 1, p - 1) % MOD);
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 5.7 MB, 提交时间: 2023-07-20 14:59:27
class Solution {
const int mod = 1000000007;
public:
int minNonZeroProduct(int p)
{
// 使用非递归的快速幂方法
// ret为最终的返回值，初始值设为2^p - 1取模后的值
// k为快速幂的指数
long long ret = ((1LL << p) - 1) % mod , k = (1LL << p - 1) - 1;
// 此写法multi最终额外乘了一次
// 如果遇到卡常数的矩阵快速幂，有可能导致超时
for(long long multi = ((1LL << p) - 2) % mod ; k ; k >>= 1)
{
if(k & 1) ret = ret * multi % mod;
multi = multi * multi % mod;
}
return ret;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-07-20 14:57:12
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)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-07-20 14:56:41
const mod int = 1e9 + 7
func minNonZeroProduct(p int) int {
return (1<<p - 1) % mod * pow(1<<p-2, 1<<(p-1)-1) % mod
}
// 快速幂，x的n次方
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
}