#1969
Minimum Non-Zero Product of the Array Elements
expert · 1100 · lc medium +32 · verified · 37.4% accepted · 283 likes · top 16%
Description
Given a positive integer p, consider the 1-indexed array of all integers from 1 to 2p - 1. You may repeatedly choose any two elements x and y and swap a specific bit between them (the bit at the same position in both). For instance, swapping the second bit from the right of x = 1101 and y = 0011 gives x = 1111 and y = 0001.
After any number of such operations, find the smallest possible non-zero product of the array. Return this minimum product modulo 109 + 7. The minimum is determined before applying the modulo.
Example 1:
Input: p = 1
Output: 1
Explanation: nums = [1].
There is only one element, so the product equals that element.
Example 2:
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:
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, 110, 011, 100, 001, 110, 111].
- In the second operation we can swap the middle bit of the third and fourth elements.
- The resulting array is [001, 110, 001, 110, 001, 110, 111].
The array product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible product.
Code
1
2
3