Minimum non zero product of the array elements

Math Greedy Recursion

37.4% acceptance

Feb 25, 2026

282

399

You are given a positive integer p. Consider an array nums (1-indexed) that consists of the integers in the inclusive range [1, 2p - 1] in their binary representations. You are allowed to do the following operation any number of times: Choose two elements x and y from nums. Choose a bit in x and swap it with its corresponding bit in y. Corresponding bit refers to the bit that is in the same position in the other integer. For example, if x = 1101 and y = 0011, after swapping the 2nd bit from the right, we have x = 1111 and y = 0001. Find the minimum non-zero product of nums after performing the above operation any number of times. Return this product modulo 109 + 7. Note: The answer should be the minimum product before the modulo operation is done.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_non_zero_product(p: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // The optimal strategy: pair up numbers to create (2^p - 2) and 1
    // Result = (2^p - 1) * (2^p - 2)^(2^(p-1) - 1)
    let max_val = ((1u64 << p) - 1) % MOD as u64; // 2^p - 1
    let base = ((1u64 << p) - 2) % MOD as u64;    // 2^p - 2
    let exp = (1u64 << (p - 1)) - 1;               // 2^(p-1) - 1
    
    let result = (max_val as i64 % MOD) * Self::pow_mod(base as i64, exp, MOD) % MOD;
    result as i32
  }
  
  fn pow_mod(mut base: i64, mut exp: u64, modulus: i64) -> i64 {
    let mut result = 1i64;
    base %= modulus;
    while exp > 0 {
      if exp & 1 == 1 {
        result = result * base % modulus;
      }
      exp >>= 1;
      base = base * base % modulus;
    }
    result
  }
}