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