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 2Entrada: 2
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>
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