Program to check if a number can be expressed as an even power of 2 or not

0 0 9 minutes read

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 2² = 4, which is an even number power of 2.

Input: N = 8
Output: No
Explanation: 8 can be expressed as 2³ = 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 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>

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 2^mid is N, and the value of mid is even, then print “Yes” and break out of the loop.
- If the value of 2^mid < 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 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>

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:

2⁰ = 00….0001
2¹ = 00….0010
2² = 00….0100
2³ = 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 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>

Output:

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