Minimum Non-Zero Product of the Array Elements in Java

假设我们有一个正整数 p，我们希望对包含 1 到 2^p - 1 的二进制数字的数组 nums 执行操作。在对数组元素执行任意次数的特定操作后，目标是找出数组元素的最小非零积。为此，从 nums 中选择任意两个元素 x 和 y，并在它们之间交换相应的位（即，x 中的某个位与 y 中的某个位进行交换）。

目标是以最小化数组中每个整数的乘积，然后以 (10^9 + 7) 取模来返回最小乘积。只需要在取模之前计算乘积。

示例 1

输入

int p = 1

输出

p 的最小非零积为：1

解释

给定 p = 1，则 2^1 -1=1，所以 base_valA 为 1。幂值 pow_valB 为 (2^1 - 2)^{2^0 - 1} \mod 10^9 + 7 = 0^{0} \mod 10^9 + 7 = 1。结果为 1 * 1 % 10^9 + 7 = 1。

示例 2

输入

int p = 4

输出

p 的最小非零积为：62748517

解释

给定 p = 4，2^4 -1 =15，所以 base_valA 为 15。幂值 pow_valB 为 (2^4 - 2)^{2^3 - 1} \mod 10^9 + 7 = 14^7 \mod 10^9 + 7 = 418211942。结果为 15 * 418211942 % 10^9 + 7 = 62748517。

示例 3

输入

int p = 2

输出

p 的最小非零积为：1

解释

给定 p = 2，则 2^2 - 1 = 3，所以 base_valA 为 3。幂值 pow_valB 为 (2^2 - 2)^{2^1 - 1} \mod 10^9 + 7 = 2^1 \mod 10^9 + 7 = 2。结果为 3 * 2 % 10^9 + 7 = 6。

我们必须考虑二进制整数的特性以及位交换的影响。考虑到我们处理的值范围从 1 到 2^p - 1，我们可以推断出，当转换为 二进制 时，这些数字将类似于从 1 到 111...111（p-1 个 1）的系列。

由于任何一组数字的乘积在数字相等或尽可能接近时最小，如果我们执行操作以最小化乘积，则应努力使数字尽可能接近。这表明我们应该努力增加最小数字的值并减小最大数字的值。但由于它是 1 且没有零可以替换它，所以最小的数字是不可变的。

朴素方法

算法

步骤 1：在长时间计算过程中，为了防止缓冲区溢出，将 Mod 设置为 10^9 + 7 (1,000,000,007)。

步骤 2：计算 2^p -1 以找到基值 a。这是通过使用表达式 (1<<p)−1 高效计算 2^p 来实现的，然后应用模 Mod 以保持可管理性。

步骤 3：将结果 res 初始化为 1，用于基数 b、指数 e 和模数 m。

步骤 4：如果 e 的最低有效位 (e&1) 为 1，则将 res 乘以 b 模 m。

步骤 5：将基数 b 除以二，将其平方模 m，并将 e 向右移动一位。

步骤 6：返回 res 作为 b^e mod m 的结果。

步骤 7：最终乘积通过将 base_valA 乘以 pow_valB 并将结果模 Mod 来计算。

步骤 8：如果最终结果已转换为整数，则返回它。

实现

文件名：MinimumNonZero.java

输出

 
The Minimum Non-Zero Product for the p is given by: 1   

复杂度分析

上述代码的时间复杂度为 O(p)，空间复杂度为 O(1)。