Dado un entero positivo N , la tarea es verificar si el entero dado es una potencia par de 2 o no.
Ejemplos:
Entrada: N = 4
Salida: Sí
Explicación: 4 se puede expresar como 2 2 = 4, que es una potencia de número par de 2.Entrada: N = 8
Salida: No
Explicación: 8 se puede expresar como 2 3 = 8, que es una potencia impar de 2.
Enfoque ingenuo: el enfoque más simple es iterar sobre todos los valores de exponente de 2 y verificar si el valor correspondiente es N y el exponente es par o no . Si se encuentra que ambos son verdaderos, imprima «Sí» . De lo contrario, si el exponente actual de 2 excede a N , imprima “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if N can be
// expressed as an even power of 2
bool checkEvenPower(int n)
{
int x = 0;
// Iterate till x is N
while (x < n) {
int value = pow(2, x);
if (value == n) {
// if x is even then
// return true
if (x % 2 == 0)
return true;
else
return false;
}
// Increment x
x++;
}
// If N is not a power of 2
return false;
}
// Driver Code
int main()
{
int N = 4;
cout << (checkEvenPower(N) ? "Yes" : "No");
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to check if N can be
// expressed as an even power of 2
static boolean checkEvenPower(int n)
{
int x = 0;
// Iterate till x is N
while (x < n)
{
int value = (int)Math.pow(2, x);
if (value == n)
{
// if x is even then
// return true
if (x % 2 == 0)
return true;
else
return false;
}
// Increment x
x++;
}
// If N is not a power of 2
return false;
}
// Driver Code
public static void main (String[] args)
{
int N = 4;
System.out.println((checkEvenPower(N) ? "Yes" : "No"));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach
# Function to check if N can be
# expressed as an even power of 2
def checkEvenPower(n):
x = 0
# Iterate till x is N
while (x < n):
value = pow(2, x)
if (value == n):
# If x is even then
# return true
if (x % 2 == 0):
return True
else:
return False
# Increment x
x += 1
# If N is not a power of 2
return False
# Driver Code
if __name__ == '__main__':
N = 4
if checkEvenPower(N):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if N can be
// expressed as an even power of 2
static bool checkEvenPower(int n)
{
int x = 0;
// Iterate till x is N
while (x < n)
{
int value = (int)Math.Pow(2, x);
if (value == n)
{
// if x is even then
// return true
if (x % 2 == 0)
return true;
else
return false;
}
// Increment x
x++;
}
// If N is not a power of 2
return false;
}
// Driver Code
static public void Main()
{
int N = 4;
Console.Write((checkEvenPower(N) ? "Yes" : "No"));
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
// Javascript program for the above approach
// Function to check if N can be
// expressed as an even power of 2
function checkEvenPower(n)
{
var x = 0;
// Iterate till x is N
while (x < n)
{
var value = Math.pow(2, x);
if (value == n)
{
// If x is even then
// return true
if (x % 2 == 0)
return true;
else
return false;
}
// Increment x
x++;
}
// If N is not a power of 2
return false;
}
// Driver code
var N = 4;
document.write((checkEvenPower(N) ? "Yes" : "No"));
// This code is contributed by Ankita saini
</script>
Producción:
Yes
Complejidad de tiempo: O(log N)
Espacio auxiliar: O(1)
Otro enfoque: el enfoque anterior también se puede implementar mediante la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos bajo como 0 y alto como N .
- Iterar hasta que lo bajo exceda lo alto :
- Encuentre el valor de mid como low + (high – low)/2 .
- Si el valor de 2 mid es N y el valor de mid es par, imprima «Sí» y salga del bucle .
- Si el valor de 2 mid < N , actualice el valor de low como (mid + 1) .
- De lo contrario, actualice el valor de high as (mid – 1) .
- Después de completar los pasos anteriores, si el bucle no se rompe, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if N can be
// expressed as an even power of 2 or not
string checkEvenPower(int n)
{
int low = 0, high = n;
// Iterate until low > high
while (low <= high) {
// Calculate mid
int mid = low + (high - low) / 2;
int value = pow(2, mid);
// If 2 ^ mid is equal to n
if (value == n) {
// If mid is odd
if (mid % 2 == 1)
return "No";
else
return "Yes";
}
// Update the value of low
else if (value < n)
low = mid + 1;
// Update the value of high
else
high = mid - 1;
}
// Otherwise
return "No";
}
// Driver Code
int main()
{
int N = 4;
cout << checkEvenPower(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if N can be
// expressed as an even power of 2 or not
static String checkEvenPower(int n)
{
int low = 0, high = n;
// Iterate until low > high
while (low <= high)
{
// Calculate mid
int mid = low + (high - low) / 2;
int value = (int) Math.pow(2, mid);
// If 2 ^ mid is equal to n
if (value == n)
{
// If mid is odd
if (mid % 2 == 1)
return "No";
else
return "Yes";
}
// Update the value of low
else if (value < n)
low = mid + 1;
// Update the value of high
else
high = mid - 1;
}
// Otherwise
return "No";
}
// Driver code
public static void main(String[] args)
{
int N = 4;
System.out.println(checkEvenPower(N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to check if N can be # expressed as an even power of 2 or not def checkEvenPower(n): low, high = 0, n # Iterate until low > high while (low <= high): # Calculate mid mid = low + (high - low) / 2 value = pow(2, mid) # If 2 ^ mid is equal to n if (value == n): # If mid is odd if (mid % 2 == 1): return "No" else: return "Yes" # Update the value of low elif (value < n): low = mid + 1 # Update the value of high else: high = mid - 1 # Otherwise return "No" # Driver code N = 4 print(checkEvenPower(N)) # This code is contributed by SoumikMondal
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if N can be
// expressed as an even power of 2 or not
static String checkEvenPower(int n)
{
int low = 0, high = n;
// Iterate until low > high
while (low <= high)
{
// Calculate mid
int mid = low + (high - low) / 2;
int value = (int) Math.Pow(2, mid);
// If 2 ^ mid is equal to n
if (value == n)
{
// If mid is odd
if (mid % 2 == 1)
return "No";
else
return "Yes";
}
// Update the value of low
else if (value < n)
low = mid + 1;
// Update the value of high
else
high = mid - 1;
}
// Otherwise
return "No";
}
// Driver code
public static void Main(String[] args)
{
int N = 4;
Console.WriteLine(checkEvenPower(N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program for the above approach
// Function to check if N can be
// expressed as an even power of 2 or not
function checkEvenPower(n)
{
var low = 0, high = n;
// Iterate until low > high
while (low <= high) {
// Calculate mid
var mid = low + (high - low) / 2;
var value = parseInt( Math.pow(2, mid));
// If 2 ^ mid is equal to n
if (value == n)
{
// If mid is odd
if (mid % 2 == 1)
return "No";
else
return "Yes";
}
// Update the value of low
else if (value < n)
low = mid + 1;
// Update the value of high
else
high = mid - 1;
}
// Otherwise
return "No";
}
// Driver code
var N = 4;
document.write(checkEvenPower(N));
// This code is contributed by gauravrajput1
</script>
Producción:
Yes
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- La representación binaria de la potencia de 2 s es de la siguiente forma:
2 0 = 00….0001
2 1 = 00….0010
2 2 = 00….0100
2 3 = 00….1000
- La observación de las representaciones binarias anteriores es que para que un número sea la potencia de 2 , debe tener solo 1 bit establecido y para ser una potencia par de 2 , entonces el único bit establecido debe estar en la posición impar.
- Por lo tanto, el número que puede diferenciar estas potencias pares e impares entre sí es 5 (0101) . Suponiendo que el valor va a caber en un entero largo de 64 bits, el AND bit a bit de 0x55555555 con N , es un número positivo si y solo si se establece un bit impar, es decir, tiene una potencia par de 2.
Por lo tanto, la idea es verificar si Bitwise AND de 0x55555555 y N es positivo, luego imprimir «Sí». De lo contrario “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if N can be
// expressed as an even power of 2 or not
bool checkEvenPower(long long int N)
{
// If N is not a power of 2
if ((N & (N - 1)) != 0)
return false;
// Bitwise AND operation
N = N & 0x55555555;
return (N > 0);
}
// Driver Code
int main()
{
int N = 4;
cout << checkEvenPower(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to check if N can be
// expressed as an even power of 2 or not
static boolean checkEvenPower(long N)
{
// If N is not a power of 2
if ((N & (N - 1)) != 0)
return false;
// Bitwise AND operation
N = N & 0x55555555;
return (N > 0);
}
// Driver Code
public static void main (String[] args)
{
long N = 4;
System.out.println(checkEvenPower(N)? 1 : 0);
}
}
// This code is contributed by rag2127
Python3
# Python3 program for the above approach # Function to check if N can be # expressed as an even power of 2 or not def checkEvenPower(N): # If N is not a power of 2 if ((N & (N - 1)) != 0): return false # Bitwise AND operation N = N & 0x55555555 return (N > 0) # Driver Code N = 4 print(1 if checkEvenPower(N) else 0) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
public class GFG {
// Function to check if N can be
// expressed as an even power of 2 or not
static bool checkEvenPower(long N) {
// If N is not a power of 2
if ((N & (N - 1)) != 0)
return false;
// Bitwise AND operation
N = N & 0x55555555;
return (N > 0);
}
// Driver Code
public static void Main(String[] args) {
long N = 4;
Console.WriteLine(checkEvenPower(N) ? 1 : 0);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if N can be
// expressed as an even power of 2 or not
function checkEvenPower(N)
{
// If N is not a power of 2
if ((N & (N - 1)) != 0)
return false;
// Bitwise AND operation
N = N & 0x55555555;
return (N > 0);
}
// Driver code
let N = 4;
document.write(checkEvenPower(N)? 1 : 0);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
1
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA