Given a positive integer N, the task is to check whether the given integer is an even power of 2 or not.
Examples:
Input: N = 4
Output: Yes
Explanation: 4 can be expressed as 22 = 4, which is an even number power of 2.Input: N = 8
Output: No
Explanation: 8 can be expressed as 23 = 8, which is an odd power of 2.
Naive Approach: The simplest approach is to iterate over all exponent values of 2 and check if the corresponding value is N and the exponent is even or not. If both are found to be true, then print “Yes”. Otherwise, if current exponent of 2 exceeds N, print “No”.
Below is the implementation of the above approach:
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 2bool 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 Codeint main(){ int N = 4; cout << (checkEvenPower(N) ? "Yes" : "No");} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to check if N can be// expressed as an even power of 2static 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 Codepublic 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 2def 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to check if N can be// expressed as an even power of 2static 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 Codestatic 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 2function 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 codevar N = 4;document.write((checkEvenPower(N) ? "Yes" : "No"));// This code is contributed by Ankita saini </script> |
Output:
Yes
Time Complexity: O(log N)
Auxiliary Space : O(1)
Another Approach: The above approach can also be implemented using Binary Search. Follow the steps below to solve the problem:
- Initialize two variables, say low as 0 and high as N.
- Iterate until low exceeds high:
- Find the value of mid as low + (high – low)/2.
- If the value of 2mid is N, and the value of mid is even, then print “Yes” and break out of the loop.
- If the value of 2mid < N, update the value of low as (mid + 1).
- Otherwise, update the value of high as (mid – 1).
- After completing the above steps, if the loop doesn’t break, then print “No”.
Below is the implementation of the above approach:
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 notstring 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 Codeint main(){ int N = 4; cout << checkEvenPower(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to check if N can be// expressed as an even power of 2 or notstatic 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 codepublic 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 notdef 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 codeN = 4print(checkEvenPower(N))# This code is contributed by SoumikMondal |
C#
// C# program for the above approachusing System;public class GFG{ // Function to check if N can be// expressed as an even power of 2 or notstatic 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 codepublic 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> |
Output:
Yes
Time Complexity: O(log N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized based on the following observations:
- Binary representation of power of 2s are of the following form:
20 = 00….0001
21 = 00….0010
22 = 00….0100
23 = 00….1000
- The observation from the above binary representations is that for a number to be the power of 2, it must have only 1 set bit and to be an even power of 2, then the only set bit should be at the odd position.
- Therefore, the number that can differentiate these even and odd powers from each other is 5 (0101). Assuming that the value is going to fit in a 64-bit long integer, the Bitwise AND of 0x55555555 with N, is a positive number if and only if an odd bit is set, i.e., having even power of 2.
Therefore, the idea is to check if Bitwise AND of 0x55555555 and N is positive, then print “Yes”. Otherwise “No”.
Below is the implementation of the above approach:
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 notbool 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 Codeint main(){ int N = 4; cout << checkEvenPower(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to check if N can be// expressed as an even power of 2 or notstatic 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 Codepublic 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 notdef 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 CodeN = 4print(1 if checkEvenPower(N) else 0)# This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approachusing 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 notfunction 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> |
Output:
1
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
