Compruebe si existe la permutación de los primeros N números naturales que tienen AND bit a bit de elementos adyacentes distintos de cero

Dado un entero N , la tarea es verificar si existe alguna permutación de los primeros N números naturales [1, N] tal que Bitwise AND de cualquier par de elementos consecutivos no sea igual a 0 . Si existe tal permutación, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos: 

Entrada: 5
Salida: Sí
Explicación: La permutación {2, 3, 1, 5, 4} satisface la condición.

Entrada: 4
Salida: No
Explicación: Dado que Bitwise AND de 4 y 3 es igual a 0, no se pueden colocar de forma adyacente. Del mismo modo, 2 y 4, 1 y 2, 1 y 4 no se pueden colocar de forma adyacente. Por lo tanto, no existe tal permutación.

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

• Si N es una potencia de dos , entonces N & (N – 1) es igual a 0 . Por lo tanto, no existe ninguna solución posible.
• De lo contrario, existe una permutación.

Por lo tanto, para resolver el problema, simplemente comprueba si N es una potencia de 2 o no . Si es falso, escriba “ Sí ”. De lo contrario, escriba “ No ”.

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

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a permutation
// of first N natural numbers exist
// with Bitwise AND of adjacent
// elements not equal to 0
void check(int n)
{
    // If n is a power of 2
    if ((n & n - 1) != 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
 
    int n = 5;
    check(n);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class solution{
     
// Function to check if a
// permutation of first N
// natural numbers exist
// with Bitwise AND of adjacent
// elements not equal to 0
static void check(int n)
{
  // If n is a power of 2
  if ((n & n - 1) != 0)
    System.out.println("YES");
  else
    System.out.println("NO");
}
 
// Driver Code
public static void main(String args[])
{
  int n = 5;
  check(n);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

# Python3 program to implement
# the above approach
 
# Function to check if a permutation
# of first N natural numbers exist
# with Bitwise AND of adjacent
# elements not equal to 0
def check(n):
     
    # If n is a power of 2
    if ((n & n - 1) != 0):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
     
    n = 5
     
    check(n)
 
# This code is contributed by bgangwar59

// C# Program to implement
// the above approach
using System;
class solution{
     
// Function to check if a
// permutation of first N
// natural numbers exist
// with Bitwise AND of adjacent
// elements not equal to 0
static void check(int n)
{
  // If n is a power of 2
  if ((n & n - 1) != 0)
    Console.WriteLine("YES");
  else
    Console.WriteLine("NO");
}
 
// Driver Code
public static void Main(String []args)
{
  int n = 5;
  check(n);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to implement
// the above approach
 
// Function to check if a
// permutation of first N
// natural numbers exist
// with Bitwise AND of adjacent
// elements not equal to 0
function check(n)
{
     
    // If n is a power of 2
    if ((n & n - 1) != 0)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver Code
var n = 5;
 
check(n);
 
// This code is contributed by umadevi9616
 
</script>

YES

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)