Class Solution
java.lang.Object
g1901_2000.s1969_minimum_non_zero_product_of_the_array_elements.Solution
1969 - Minimum Non-Zero Product of the Array Elements.<p>Medium</p>
<p>You are given a positive integer <code>p</code>. Consider an array <code>nums</code> ( <strong>1-indexed</strong> ) that consists of the integers in the <strong>inclusive</strong> range <code>[1, 2<sup>p</sup> - 1]</code> in their binary representations. You are allowed to do the following operation <strong>any</strong> number of times:</p>
<ul>
<li>Choose two elements <code>x</code> and <code>y</code> from <code>nums</code>.</li>
<li>Choose a bit in <code>x</code> and swap it with its corresponding bit in <code>y</code>. Corresponding bit refers to the bit that is in the <strong>same position</strong> in the other integer.</li>
</ul>
<p>For example, if <code>x = 1101</code> and <code>y = 0011</code>, after swapping the <code>2<sup>nd</sup></code> bit from the right, we have <code>x = 1111</code> and <code>y = 0001</code>.</p>
<p>Find the <strong>minimum non-zero</strong> product of <code>nums</code> after performing the above operation <strong>any</strong> number of times. Return <em>this product</em> <em><strong>modulo</strong></em> <code>10<sup>9</sup> + 7</code>.</p>
<p><strong>Note:</strong> The answer should be the minimum product <strong>before</strong> the modulo operation is done.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> p = 1</p>
<p><strong>Output:</strong> 1</p>
<p><strong>Explanation:</strong> nums = [1]. There is only one element, so the product equals that element.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> p = 2</p>
<p><strong>Output:</strong> 6</p>
<p><strong>Explanation:</strong> nums = [01, 10, 11].</p>
<p>Any swap would either make the product 0 or stay the same.</p>
<p>Thus, the array product of 1 * 2 * 3 = 6 is already minimized.</p>
<p><strong>Example 3:</strong></p>
<p><strong>Input:</strong> p = 3</p>
<p><strong>Output:</strong> 1512</p>
<p><strong>Explanation:</strong> nums = [001, 010, 011, 100, 101, 110, 111]</p>
<ul>
<li>
<p>In the first operation we can swap the leftmost bit of the second and fifth elements.</p>
<ul>
<li>The resulting array is [001, 110, 011, 100, 001, 110, 111].</li>
</ul>
</li>
<li>
<p>In the second operation we can swap the middle bit of the third and fourth elements.</p>
<ul>
<li>The resulting array is [001, 110, 001, 110, 001, 110, 111].</li>
</ul>
</li>
</ul>
<p>The array product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible product.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= p <= 60</code></li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
minNonZeroProduct
public int minNonZeroProduct(int p)
-