本文主要是介绍LeetCode解法汇总1969. 数组元素的最小非零乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录链接：
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目：
https://github.com/September26/java-algorithms
原题链接：. - 力扣（LeetCode）
描述：
给你一个正整数 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
解题思路：
首先，我们了解一个概念，两个数之和不变时，大的数越大，小的数越小，则乘积就越小。比如之和为8，则1*7最小，4*4最大。所以这道题，我们就是要让大的数越大，小的数越小。
以p=3为例，有7个数：[1，2，3，4，5，6，7]，1和7无法加减，则让2和5结合，2和4结合。得到[1,1,1,6,6,6,7]。
总结规律：有2^(p-1)-1个1 以及 2^(p-1)-1个2^p-2，以及1个2^p-1。
1可以忽略，则最终就是 2^(p-1)-1个2^p-2和1个2^p-1的乘积。
代码：
class Solution {public int minNonZeroProduct(int p) {if (p == 1) {return 1;}long mod = 1000000007;long x = fastPow(2, p, mod) - 1;long y = (long) 1 << (p - 1);return (int) (fastPow(x - 1, y - 1, mod) * x % mod);}public long fastPow(long x, long n, long mod) {long res = 1;for (; n != 0; n >>= 1) {if ((n & 1) != 0) {res = res * x % mod;}x = x * x % mod;}return res;}
}这篇关于LeetCode解法汇总1969. 数组元素的最小非零乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
