# Minimize product of first 2^K–1 Natural Numbers by swapping bits for any pair any number of times

Given a positive integer **K**, the** **task is to minimize the positive product of the first **(2 ^{K} – 1)** Natural Numbers by swapping the bits at the corresponding position of any two numbers any number of times.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:K = 3Output:1512Explanation: The original product is 5040. The given array in binary notation is {001, 010, 011, 100, 101, 110, 111}

- In the first operation 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 swap the middle bit of the third and fourth elements. The resulting array is [001, 110, 001, 110, 001, 110, 111].
After the above operations, the array elements are {1, 6, 1, 6, 1, 6, 7}. Therefore, the product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible positive product.

Input:K = 2Output:6Explanation: The original permutation in binary notation is {’00’, ’01’, ’10’}. Any swap will lead to product zero or does not change at all. Hence 6 is the correct output.

**Approach:** The given problem can be solved based on the observation that to get the minimum positive product the frequency of the number **1** should be maximum by swapping the bits of any two numbers. Follow the steps below to solve the given problem:

- Find the value of the
**range**as**(2**.^{K}– 1) - Convert
**range/2**elements to 1 by shifting all bits of odd numbers to even numbers except the**0**.^{th}bit - Therefore,
**range/2**numbers will be 1 and**range/2**numbers will be**range – 1**, and the last number in the array will remain the same as the value of the**range**. - Find the resultant product of all the numbers formed in the above step as the resultant minimum positive product obtained.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the minimum positive` `// product after swapping bits at the` `// similar position for any two numbers` `int` `minimumPossibleProduct(` `int` `K)` `{` ` ` `// Stores the resultant number` ` ` `int` `res = 1;` ` ` `int` `range = (1 << K) - 1;` ` ` `// range/2 numbers will be 1 and` ` ` `// range/2 numbers will be range-1` ` ` `for` `(` `int` `i = 0; i < K; i++) {` ` ` `res *= (range - 1);` ` ` `}` ` ` `// Multiply with the final number` ` ` `res *= range;` ` ` `// Return the answer` ` ` `return` `res;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `K = 3;` ` ` `cout << minimumPossibleProduct(K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to find the minimum positive` `// product after swapping bits at the` `// similar position for any two numbers` `static` `int` `minimumPossibleProduct(` `int` `K)` `{` ` ` `// Stores the resultant number` ` ` `int` `res = ` `1` `;` ` ` `int` `range = (` `1` `<< K) - ` `1` `;` ` ` `// range/2 numbers will be 1 and` ` ` `// range/2 numbers will be range-1` ` ` `for` `(` `int` `i = ` `0` `; i < K; i++) {` ` ` `res *= (range - ` `1` `);` ` ` `}` ` ` `// Multiply with the final number` ` ` `res *= range;` ` ` `// Return the answer` ` ` `return` `res;` `}` ` ` `// Driver Code` `public` `static` `void` `main (String[] args) {` ` ` ` ` `int` `K = ` `3` `;` ` ` `System.out.println(minimumPossibleProduct(K));` `}` `}` `// This code is contributed by Dharanendra L V.` |

## Python3

`# python program for the above approach` `# Function to find the minimum positive` `# product after swapping bits at the` `# similar position for any two numbers` `def` `minimumPossibleProduct(K):` ` ` ` ` `# Stores the resultant number` ` ` `res ` `=` `1` ` ` `r ` `=` `(` `1` `<< K) ` `-` `1` ` ` ` ` `# range/2 numbers will be 1 and` ` ` `# range/2 numbers will be range-1` ` ` `for` `i ` `in` `range` `(` `0` `, K):` ` ` `res ` `*` `=` `(r ` `-` `1` `)` ` ` `# Multiply with the final number` ` ` `res ` `*` `=` `r` ` ` `# Return the answer` ` ` `return` `res` `# Driver Code` `K ` `=` `3` `print` `(minimumPossibleProduct(K))` `# This code is contributed by amreshkumar3.` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG {` ` ` `// Function to find the minimum positive` ` ` `// product after swapping bits at the` ` ` `// similar position for any two numbers` ` ` `static` `int` `minimumPossibleProduct(` `int` `K)` ` ` `{` ` ` ` ` `// Stores the resultant number` ` ` `int` `res = 1;` ` ` `int` `range = (1 << K) - 1;` ` ` `// range/2 numbers will be 1 and` ` ` `// range/2 numbers will be range-1` ` ` `for` `(` `int` `i = 0; i < K; i++) {` ` ` `res *= (range - 1);` ` ` `}` ` ` `// Multiply with the final number` ` ` `res *= range;` ` ` `// Return the answer` ` ` `return` `res;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(` `string` `[] args)` ` ` `{` ` ` `int` `K = 3;` ` ` `Console.WriteLine(minimumPossibleProduct(K));` ` ` `}` `}` `// This code is contributed by ukasp.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to find the minimum positive` ` ` `// product after swapping bits at the` ` ` `// similar position for any two numbers` ` ` `function` `minimumPossibleProduct(K)` ` ` `{` ` ` ` ` `// Stores the resultant number` ` ` `let res = 1;` ` ` `let range = (1 << K) - 1;` ` ` `// range/2 numbers will be 1 and` ` ` `// range/2 numbers will be range-1` ` ` `for` `(let i = 0; i < K; i++) {` ` ` `res *= (range - 1);` ` ` `}` ` ` `// Multiply with the final number` ` ` `res *= range;` ` ` `// Return the answer` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `let K = 3;` ` ` `document.write(minimumPossibleProduct(K));` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

1512

**Time Complexity:** O(K)**Auxiliary Space:** O(1)