Minimice el producto de los primeros 2^K–1 números naturales intercambiando bits por cualquier par cualquier cantidad de veces

Dado un entero positivo K , la tarea es minimizar el producto positivo de los primeros (2 ^K – 1) Números Naturales intercambiando los bits en la posición correspondiente de dos números cualquier cantidad de veces.

Ejemplos:

Entrada: K = 3
Salida: 1512
Explicación : el producto original es 5040. La array dada en notación binaria es {001, 010, 011, 100, 101, 110, 111}

• En la primera operación, intercambie el bit más a la izquierda de los elementos segundo y quinto. La array resultante es [001, 110, 011, 100, 001, 110, 111].
• En la segunda operación, intercambie el bit medio del tercer y cuarto elemento. La array resultante es [001, 110, 001, 110, 001, 110, 111].

Después de las operaciones anteriores, los elementos de la array son {1, 6, 1, 6, 1, 6, 7}. Por tanto, el producto es 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, que es el mínimo producto positivo posible.

Entrada: K = 2
Salida: 6
Explicación : la permutación original en notación binaria es {’00’, ’01’, ’10’}. Cualquier intercambio conducirá al producto cero o no cambiará en absoluto. Por lo tanto, 6 es la salida correcta.

Enfoque: El problema dado se puede resolver basándose en la observación de que para obtener el producto positivo mínimo, la frecuencia del número 1 debe ser máxima intercambiando los bits de dos números cualesquiera. Siga los pasos a continuación para resolver el problema dado:

• Encuentra el valor del rango como (2 ^K – 1) .
• Convierta los elementos de rango/2 en 1 cambiando todos los bits de números impares a números pares excepto el ^bit 0 .
• Por lo tanto, los números de rango/2 serán 1 y los números de rango/2 serán rango – 1 , y el último número de la array seguirá siendo el mismo que el valor del rango .
• Encuentre el producto resultante de todos los números formados en el paso anterior como el producto positivo mínimo resultante obtenido.

A continuación se muestra la implementación del enfoque anterior:

// 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 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.

# 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# 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.

<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>

1512

Complejidad temporal: O(K)
Espacio auxiliar: O(1)