Minimum Non-Zero Product of the Array Elements

Problem

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 = 11 _0_ 1 and y = 00 _1_ 1, after swapping the 2nd bit from the right, we have x = 11 _1_ 1 and y = 00 _0_ 1.

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.

Examples

Example 1

1
2
3
4


Input: p = 1
Output: 1
Explanation: nums = [1].
There is only one element, so the product equals that element.

Example 2

1
2
3
4
5


Input: p = 2
Output: 6
Explanation: nums = [01, 10, 11].
Any swap would either make the product 0 or stay the same.
Thus, the array product of 1 * 2 * 3 = 6 is already minimized.

Example 3

1
2
3
4
5
6
7
8


Input: p = 3
Output: 1512
Explanation: nums = [001, 010, 011, 100, 101, 110, 111]
- In the first operation we can swap the leftmost bit of the second and fifth elements.
    - The resulting array is [001, _1_ 10, 011, 100, _0_ 01, 110, 111].
- In the second operation we can swap the middle bit of the third and fourth elements.
    - The resulting array is [001, 110, 0 _0_ 1, 1 _1_ 0, 001, 110, 111].
The array product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible product.

Constraints

1 <= p <= 60

Solution

Method 1 – Fast Modular Exponentiation (Greedy)

Intuition

The minimum product is achieved by maximizing the number of elements set to 2^p - 2 and one element set to 2^p - 1. This is because swapping bits can make all but one element as small as possible, and one as large as possible.

Approach

Let max_num = 2^p - 1 and second = max_num - 1.
Set one element to max_num, and the rest to second.
The answer is (second ^ (max_num // 2)) * max_num % MOD, where MOD = 10^9 + 7.
Use fast modular exponentiation to compute powers efficiently.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int minNonZeroProduct(int p) {
        long long MOD = 1e9 + 7;
        long long max_num = (1LL << p) - 1;
        long long second = max_num - 1;
        long long cnt = max_num / 2;
        auto mod_pow = [](long long a, long long b, long long mod) {
            long long res = 1;
            while (b) {
                if (b & 1) res = res * a % mod;
                a = a * a % mod;
                b >>= 1;
            }
            return res;
        };
        return (mod_pow(second, cnt, MOD) * max_num) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func minNonZeroProduct(p int) int {
    mod := int(1e9 + 7)
    maxNum := (1 << p) - 1
    second := maxNum - 1
    cnt := maxNum / 2
    modPow := func(a, b, mod int) int {
        res := 1
        for b > 0 {
            if b&1 == 1 {
                res = res * a % mod
            }
            a = a * a % mod
            b >>= 1
        }
        return res
    }
    return modPow(second, cnt, mod) * maxNum % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public int minNonZeroProduct(int p) {
        long MOD = 1000000007;
        long maxNum = (1L << p) - 1;
        long second = maxNum - 1;
        long cnt = maxNum / 2;
        return (int)((modPow(second, cnt, MOD) * maxNum) % MOD);
    }
    private long modPow(long a, long b, long mod) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun minNonZeroProduct(p: Int): Int {
        val MOD = 1_000_000_007L
        val maxNum = (1L shl p) - 1
        val second = maxNum - 1
        val cnt = maxNum / 2
        fun modPow(a: Long, b: Long, mod: Long): Long {
            var res = 1L
            var aa = a
            var bb = b
            while (bb > 0) {
                if (bb and 1L == 1L) res = res * aa % mod
                aa = aa * aa % mod
                bb = bb shr 1
            }
            return res
        }
        return ((modPow(second, cnt, MOD) * maxNum) % MOD).toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        MOD: int = 10**9 + 7
        max_num: int = (1 << p) - 1
        second: int = max_num - 1
        cnt: int = max_num // 2
        def mod_pow(a: int, b: int, mod: int) -> int:
            res = 1
            while b:
                if b & 1:
                    res = res * a % mod
                a = a * a % mod
                b >>= 1
            return res
        return mod_pow(second, cnt, MOD) * max_num % MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


impl Solution {
    pub fn min_non_zero_product(p: i32) -> i32 {
        let modv = 1_000_000_007;
        let max_num = (1u64 << p) - 1;
        let second = max_num - 1;
        let cnt = max_num / 2;
        fn mod_pow(mut a: u64, mut b: u64, modv: u64) -> u64 {
            let mut res = 1u64;
            while b > 0 {
                if b & 1 == 1 { res = res * a % modv; }
                a = a * a % modv;
                b >>= 1;
            }
            res
        }
        ((mod_pow(second, cnt, modv) * max_num) % modv) as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    minNonZeroProduct(p: number): number {
        const MOD = 1e9 + 7;
        const maxNum = (1 << p) - 1;
        const second = maxNum - 1;
        const cnt = Math.floor(maxNum / 2);
        function modPow(a: number, b: number, mod: number): number {
            let res = 1;
            while (b > 0) {
                if (b & 1) res = res * a % mod;
                a = a * a % mod;
                b >>= 1;
            }
            return res;
        }
        return modPow(second, cnt, MOD) * maxNum % MOD;
    }
}

Complexity

⏰ Time complexity: O(log n), for fast exponentiation.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Fast Modular Exponentiation (Greedy)#

Intuition#

Approach#

Code#

Complexity#