Permutación de los primeros N números naturales que tienen un producto de Bitwise AND de pares adyacentes superior a 0

Dado un entero positivo N , la tarea es encontrar la permutación de los primeros N números naturales tal que el producto de Bitwise AND( & ) de pares de elementos adyacentes sea mayor que 0 . Si no se encuentra tal permutación, imprima «No es posible» .

Ejemplos:

Entrada: N = 3 
Salida: 1 3 2 
Explicación: 
1 & 3 = 1 
3 & 2 = 2 
Producto de AND bit a bit de elementos adyacentes = 1 * 2 = 2(>0) 
Por lo tanto, la salida requerida es 1 3 2

Entrada:
Salida: No es posible 
Explicación: 
Las permutaciones posibles de los primeros N(= 2) números naturales son: { { 1, 2 }, { 2, 1 } } 
1 y 2 = 0 
2 y 1 = 0 
Por lo tanto, la salida requerida no es posible.

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las permutaciones posibles de los primeros N números naturales . Para cada permutación, compruebe si el producto de AND bit a bit de sus elementos adyacentes es mayor que 0 o no. Si se encuentra que es cierto, imprima esa permutación. De lo contrario, imprima «No es posible»

Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)

Enfoque eficiente: el problema se puede resolver con base en las siguientes observaciones:

Si N es una potencia de 2 , entonces el AND bit a bit de N con cualquier número menor que N debe ser 0.

Si el AND bit a bit de los elementos adyacentes es igual a 0, entonces el producto del AND bit a bit de su elemento adyacente debe ser 0.

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

  • Si N es una potencia de 2 , imprima «No es posible» .
  • Inicialice una array, digamos, arr[] para almacenar la permutación de los primeros N números naturales que satisfacen la condición dada.
  • Iterar sobre el rango [1, N] y actualizar arr[i] = i
  • Actualice los primeros tres elementos de la array de modo que el AND bit a bit de sus elementos adyacentes debe ser mayor que 0 , es decir, arr[1] = 2 , arr[2] = 3 y arr[3] = 1
  • Iterar sobre el rango [4, N] . Para cada i -ésimo valor, verifica si i es una potencia de 2 o no. Si se determina que es cierto, entonces swap(arr[i], arr[i+1]) .
  • Finalmente, imprima el arr[] .

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number
// is a power of 2 or not
bool isPowerOfTwo(int n)
{
    if (n == 0)
        return false;
 
    return (ceil(log2(n))
            == floor(log2(n)));
}
 
// Function to find the permutation of first N
// natural numbers such that the product of
// bitwise AND  of adjacent elements is > 0
void findThePermutation(int N)
{
 
    // Base Case, If N = 1, print 1
    if (N == 1) {
        cout << "1";
        return;
    }
 
    // If N is a power of 2,
    // print "Not Possible"
    if (isPowerOfTwo(N)) {
        cout << "Not Possible";
        return;
    }
 
    // Stores permutation of first N
    // natural numbers that satisfy
    // the condition
    int arr[N + 1];
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Update arr[i]
        arr[i] = i;
    }
 
    // Update arr[1], arr[2] and arr[3]
    arr[1] = 2, arr[2] = 3, arr[3] = 1;
 
    // Iterate over the range [4, N]
    for (int i = 4; i <= N; i++) {
 
        // If i is a power of 2
        if (isPowerOfTwo(i)) {
 
            // Swap adjacent elements
            swap(arr[i], arr[i + 1]);
 
            // Update i
            i++;
        }
    }
 
    // Print the array
    for (int i = 1; i <= N; i++)
        cout << arr[i] << " ";
}
 
// Driver Code
int main()
{
    // Input
    int N = 5;
 
    // Function Call
    findThePermutation(N);
 
    return 0;
}

Java

// Java program to implement the above approach
class GFG
{
 
    // Function to calculate the
    // log base 2 of an integer
    public static int log2(int N)
    {
   
        // calculate log2 N indirectly
        // using log() method
        int result = (int)(Math.log(N) / Math.log(2));  
        return result;
    }
     
    // Function to check if a number
    // is a power of 2 or not
    static boolean isPowerOfTwo(int n)
    {
        if (n == 0)
            return false;   
        return Math.ceil(log2(n)) == Math.floor(log2(n));
    }
     
    // Function to find the permutation of first N
    // natural numbers such that the product of
    // bitwise AND  of adjacent elements is > 0
    static void findThePermutation(int N)
    {
     
        // Base Case, If N = 1, print 1
        if (N == 1)
        {
            System.out.print("1");
            return;
        }
     
        // If N is a power of 2,
        // print "Not Possible"
        if (isPowerOfTwo(N) == false)
        {
            System.out.print("Not Possible");
            return;
        }
     
        // Stores permutation of first N
        // natural numbers that satisfy
        // the condition
        int arr[] = new int[N + 1];
     
        // Iterate over the range [1, N]
        for (int i = 1; i <= N; i++)
        {
     
            // Update arr[i]
            arr[i] = i;
        }
     
        // Update arr[1], arr[2] and arr[3]
        arr[1] = 2; arr[2] = 3; arr[3] = 1;  
        int temp;
         
        // Iterate over the range [4, N]
        for (int i = 4; i <= N; i++)
        {
     
            // If i is a power of 2
            if (isPowerOfTwo(i) == true)
            {
     
                // Swap adjacent elements
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp ;
                 
                // Update i
                i++;
            }
        }
     
        // Print the array
        for (int i = 1; i <= N; i++)
            System.out.print(arr[i] + " ");
    }
     
    // Driver Code
    public static void main(String[] args)
    {
       
        // Input
        int N = 5;
     
        // Function Call
        findThePermutation(N);
    }
}
 
// This code is contributed by AnkThon

Python3

# Python3 program to implement
# the above approach
from math import ceil, floor, log2
 
# Function to check if a number
# is a power of 2 or not
def isPowerOfTwo(n):
     
    if (n == 0):
        return False
         
    return (ceil(log2(n)) == floor(log2(n)))
 
# Function to find the permutation of first N
# natural numbers such that the product of
# bitwise AND of adjacent elements is > 0
def findThePermutation(N):
     
    # Base Case, If N = 1, pr1
    if (N == 1):
        print("1")
        return
 
    # If N is a power of 2,
    # print "Not Possible"
    if (isPowerOfTwo(N)):
        print("Not Possible")
        return
 
    # Stores permutation of first N
    # natural numbers that satisfy
    # the condition
    arr = [i for i in range(N + 1)]
 
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
         
        # Update arr[i]
        arr[i] = i
 
    # Update arr[1], arr[2] and arr[3]
    arr[1], arr[2], arr[3] = 2, 3, 1
     
    # Iterate over the range [4, N]
    for i in range(4, N + 1):
         
        # If i is a power of 2
        if (isPowerOfTwo(i)):
             
            # Swap adjacent elements
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
 
            # Update i
            i += 1
 
    # Print the array
    for i in range(1, N + 1):
        print(arr[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Input
    N = 5
     
    # Function Call
    findThePermutation(N)
 
# This code is contributed by mohit kumar 29

C#

// C# program to implement the above approach
using System;
class GFG
{
 
    // Function to calculate the
    // log base 2 of an integer
    public static int log2(int N)
    {
   
        // calculate log2 N indirectly
        // using log() method
        int result = (int)(Math.Log(N) / Math.Log(2));  
        return result;
    }
     
    // Function to check if a number
    // is a power of 2 or not
    static bool isPowerOfTwo(int n)
    {
        if (n == 0)
            return false;   
        return Math.Ceiling((double)log2(n)) ==
          Math.Floor((double)log2(n));
    }
     
    // Function to find the permutation of first N
    // natural numbers such that the product of
    // bitwise AND  of adjacent elements is > 0
    static void findThePermutation(int N)
    {
     
        // Base Case, If N = 1, print 1
        if (N == 1)
        {
            Console.Write("1");
            return;
        }
     
        // If N is a power of 2,
        // print "Not Possible"
        if (isPowerOfTwo(N) == false)
        {
            Console.Write("Not Possible");
            return;
        }
     
        // Stores permutation of first N
        // natural numbers that satisfy
        // the condition
        int []arr = new int[N + 1];
     
        // Iterate over the range [1, N]
        for (int i = 1; i <= N; i++)
        {
     
            // Update arr[i]
            arr[i] = i;
        }
     
        // Update arr[1], arr[2] and arr[3]
        arr[1] = 2; arr[2] = 3; arr[3] = 1;  
        int temp;
         
        // Iterate over the range [4, N]
        for (int i = 4; i <= N; i++)
        {
     
            // If i is a power of 2
            if (isPowerOfTwo(i) == true)
            {
     
                // Swap adjacent elements
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp ;
                 
                // Update i
                i++;
            }
        }
     
        // Print the array
        for (int i = 1; i <= N; i++)
            Console.Write(arr[i] + " ");
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
       
        // Input
        int N = 5;
     
        // Function Call
        findThePermutation(N);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to implement
// the above approach   
 
   // Function to calculate the
  // log base 2 of an integer
    function log2(N) {
 
        // calculate log2 N indirectly
        // using log() method
        var result = parseInt( (Math.log(N) / Math.log(2)));
        return result;
    }
 
    // Function to check if a number
    // is a power of 2 or not
    function isPowerOfTwo(n) {
        if (n == 0)
            return false;
        return Math.ceil(log2(n)) == Math.floor(log2(n));
    }
 
    // Function to find the permutation of first N
    // natural numbers such that the product of
    // bitwise AND of adjacent elements is > 0
    function findThePermutation(N) {
 
        // Base Case, If N = 1, print 1
        if (N == 1) {
            document.write("1");
            return;
        }
 
        // If N is a power of 2,
        // print "Not Possible"
        if (isPowerOfTwo(N) == false) {
            document.write("Not Possible");
            return;
        }
 
        // Stores permutation of first N
        // natural numbers that satisfy
        // the condition
        var arr = Array(N + 1).fill(0);
 
        // Iterate over the range [1, N]
        for (i = 1; i <= N; i++) {
 
            // Update arr[i]
            arr[i] = i;
        }
 
        // Update arr[1], arr[2] and arr[3]
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 1;
        var temp;
 
        // Iterate over the range [4, N]
        for (i = 4; i <= N; i++) {
 
            // If i is a power of 2
            if (isPowerOfTwo(i) == true) {
 
                // Swap adjacent elements
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
 
                // Update i
                i++;
            }
        }
 
        // Print the array
        for (i = 1; i <= N; i++)
            document.write(arr[i] + " ");
    }
 
    // Driver Code
     
 
        // Input
        var N = 5;
 
        // Function Call
        findThePermutation(N);
 
// This code is contributed by todaysgaurav
 
</script>
Producción: 

2 3 1 5 4

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *