Minimice el producto de los primeros N – 1 números naturales intercambiando bits de pares en la misma posición

Dado un número entero N , la tarea es encontrar el producto positivo mínimo de los primeros N – 1 números naturales, es decir, [1, (N – 1)] , intercambiando cualquier i ^-ésimo bit de dos números cualquiera cualquier número de veces.

Nota: N es siempre una potencia perfecta de 2 . Como el producto puede ser muy grande, imprima la respuesta módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: N = 4
Salida: 6
Explicación:
No se requiere intercambio de bits. Por lo tanto, el producto mínimo es 1*2*3 = 6.

Entrada: N = 8
Salida: 1512
Explicación:
Deje que la array arr[] almacene todos los valores de 1 a N como {1, 2, 3, 4, 5, 6, 7}
Siga los pasos a continuación:
Paso 1: En elementos 2 = (0010) y 5 = (0101), intercambiar 0 y 1 bit. Por lo tanto, reemplaza 2 con 1 y 5 con 6. arr[] = {1, 1, 3, 4, 6, 6, 7}.
Paso 2: En los elementos 3 = (0011) y 4 = (0100), intercambie el 1.° bit. Por lo tanto, reemplaza 3 con 1 y 4 con 6. arr[] = {1, 1, 1, 6, 6, 6, 7}.
Por tanto, el producto mínimo = 1*1*1*6*6*6*7 = 1512 % 1e9+7 = 1512.

Planteamiento: La idea es hacer algunas observaciones. Por ejemplo, si N = 8 y arr[] = {1, 2, 3, 4, 5, 6, 7} , observe que para que el producto sea mínimo debe haber tres seises, es decir, debe haber un elemento que tenga valor (N – 2) con la frecuencia de ocurrencia como (1 + (N – 4)/2)  y debe haber tres unos, es decir, debe haber (1 + (N – 4)/2) unos. Y por último multiplica el producto actual por (N – 1) . Por lo tanto, la fórmula se convierte en:

Producto mínimo para cualquier valor N = ((N – 1) * (N – 2) ^{(N – 4)/2 + 1} ) % 1e9 + 7 

Siga los pasos a continuación para resolver el problema:

1. Inicialice el ans como 1 .
2. Iterar sobre el rango [0, 1 + (N – 4)/2] .
3. En cada recorrido, multiplique ans con N – 2 y actualice ans a ans mod 1e9+7 .
4. Después de los pasos anteriores, imprima el valor de ans*(N – 1) mod 1e9+7 como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int mod = 1e9 + 7;
 
// Function to find the minimum product
// of 1 to N - 1 after performing the
// given operations
void minProduct(int n)
{
    // Initialize ans with 1
    int ans = 1;
 
    // Multiply ans with N-2
    // ((N - 4)/2) times
    for (int i = 1;
         i <= (n - 4) / 2; i++) {
        ans = (1LL * ans
               * (n - 2))
              % mod;
    }
 
    // Multiply ans with N - 1
    // and N - 2 once
    ans = (1LL * ans
           * (n - 2) * (n - 1))
          % mod;
 
    // Print ans
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    // Given Number N
    int N = 8;
 
    // Function Call
    minProduct(N);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
static int mod = (int)1e9 + 7;
 
// Function to find the
// minimum product of 1
// to N - 1 after performing
// the given operations
static void minProduct(int n)
{
  // Initialize ans with 1
  int ans = 1;
 
  // Multiply ans with N-2
  // ((N - 4)/2) times
  for (int i = 1;
           i <= (n - 4) / 2; i++)
  {
    ans = (int)(1L * ans *
               (n - 2)) % mod;
  }
 
  // Multiply ans with N - 1
  // and N - 2 once
  ans = (int)(1L * ans *
             (n - 2) * (n - 1)) % mod;
 
  // Print ans
  System.out.print(ans + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given Number N
  int N = 8;
 
  // Function Call
  minProduct(N);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
mod = 1e9 + 7
 
# Function to find the minimum product
# of 1 to N - 1 after performing the
# given operations
def minProduct(n):
     
    # Initialize ans with 1
    ans = 1
 
    # Multiply ans with N-2
    # ((N - 4)/2) times
    for i in range(1, (n - 4) // 2 + 1):
        ans = (ans * (n - 2)) % mod
 
    # Multiply ans with N - 1
    # and N - 2 once
    ans = (ans * (n - 2) * (n - 1)) % mod
 
    # Print ans
    print(int(ans))
 
# Driver Code
if __name__ == '__main__':
     
    # Given number N
    N = 8
 
    # Function call
    minProduct(N)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
class GFG{
 
static int mod = (int)1e9 + 7;
 
// Function to find the
// minimum product of 1
// to N - 1 after performing
// the given operations
static void minProduct(int n)
{
  // Initialize ans with 1
  int ans = 1;
 
  // Multiply ans with N-2
  // ((N - 4)/2) times
  for (int i = 1;
           i <= (n - 4) / 2; i++)
  {
    ans = (int)(1L * ans *
               (n - 2)) % mod;
  }
 
  // Multiply ans with N - 1
  // and N - 2 once
  ans = (int)(1L * ans *
             (n - 2) *
             (n - 1)) % mod;
 
  // Print ans
  Console.Write(ans + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given Number N
  int N = 8;
 
  // Function Call
  minProduct(N);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// JavaScript program for the above approach
 
let mod = 1e9 + 7;
 
// Function to find the minimum product
// of 1 to N - 1 after performing the
// given operations
function minProduct(n)
{
    // Initialize ans with 1
    let ans = 1;
 
    // Multiply ans with N-2
    // ((N - 4)/2) times
    for (let i = 1; i <= Math.floor((n - 4) / 2); i++)
    {
        ans = (1 * ans * (n - 2)) % mod;
    }
 
    // Multiply ans with N - 1
    // and N - 2 once
    ans = (1 * ans * (n - 2) * (n - 1)) % mod;
 
    // Print ans
    document.write(ans + "<br>");
}
 
// Driver Code
 
    // Given Number N
    let N = 8;
 
    // Function Call
    minProduct(N);
 
// This code is contributed by Manoj.
</script>

1512

Complejidad de tiempo: O(N) donde N es el número entero dado.
Espacio Auxiliar: O(1)