Check if a number can be represented as sum of non zero powers of 2

0 0 5 minutes read

Given an integer N, the task is to check whether N can be represented as the sum of powers of 2 where all the powers are > 0 i.e. 2⁰ cannot contribute to the sum.
Examples:

Input: N = 10
Output: 1
2³ + 2¹ = 10
Input: N = 9
Output: 0

Approach: There are two cases:

When N is even then it can always be represented as the sum of powers of 2 when power > 0.
When N is odd then it can never be represented as the sum of powers of 2 if 2⁰ is not included in the sum.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that return true if n
// can be represented as the sum
// of powers of 2 without using 2^0
bool isSumOfPowersOfTwo(int n)
{
    if (n % 2 == 1)
        return false;
    else
        return true;
}
 
// Driver code
int main()
{
    int n = 10;
    if (isSumOfPowersOfTwo(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
class GFG {
 
    // Function that return true if n
    // can be represented as the sum
    // of powers of 2 without using 2^0
    static boolean isSumOfPowersOfTwo(int n)
    {
        if (n % 2 == 1)
            return false;
        else
            return true;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 10;
        if (isSumOfPowersOfTwo(n))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

Python3

# Python3 implementation of the approach 
 
# Function that return true if n 
# can be represented as the sum 
# of powers of 2 without using 2^0
def isSumOfPowersOfTwo(n):
    if n % 2 == 1:
        return False
    else:
        return True
 
# Driver code
n = 10
if isSumOfPowersOfTwo(n):
    print("Yes")
else:
    print("No")
 
# This code is contributed
# by Shrikant13

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function that return true if n
    // can be represented as the sum
    // of powers of 2 without using 2^0
    static bool isSumOfPowersOfTwo(int n)
    {
        if (n % 2 == 1)
            return false;
        else
            return true;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 10;
        if (isSumOfPowersOfTwo(n))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

Javascript

<script>
// Javascript implementation of the approach
 
// Function that return true if n
// can be represented as the sum
// of powers of 2 without using 2^0
function isSumOfPowersOfTwo(n)
{
    if (n % 2 == 1)
        return false;
    else
        return true;
}
 
// Driver code
var n = 10;
if (isSumOfPowersOfTwo(n))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by noob2000.
</script>

PHP

<?php
// PHP implementation of the approach
 
// Function that return true if n
// can be represented as the sum
// of powers of 2 without using 2^0
function isSumOfPowersOfTwo($n)
{
    if ($n % 2 == 1)
        return false;
    else
        return true;
}
 
// Driver code
$n = 10;
if (isSumOfPowersOfTwo($n))
    echo("Yes");
else
    echo("No");
 
// This code is contributed 
// by Code_Mech
?>

Output

Yes

Time Complexity: O(1)

Auxiliary Space: O(1)

Approach 2:

Here’s another approach to solve the problem:

Start with the given number n.
Initialize a variable i to 1.
While i is less than n, do the following steps:
a. If i is a power of 2, compute n-i.
b. If n-i is also a power of 2, return true.
c. Increment i by 1.
If none of the pairs (i, n-i) are both powers of 2, return false.

Here’s the code for the above approach:

C++

#include <iostream>
#include <cmath>
using namespace std;
 
bool isPowerOfTwo(int n) {
    if (n == 0) {
        return false;
    }
    return (ceil(log2(n)) == floor(log2(n)));
}
 
bool canSumToPowerOfTwo(int n) {
    for (int i = 1; i < n; i++) {
        if (isPowerOfTwo(i) && isPowerOfTwo(n-i)) {
            return true;
        }
    }
    return false;
}
 
int main() {
    int n = 10;
    if (canSumToPowerOfTwo(n)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Java

import java.lang.Math;
 
public class PowerOfTwo {
 
    public static boolean isPowerOfTwo(int n) {
        if (n == 0) {
            return false;
        }
        return (Math.ceil(Math.log(n) / Math.log(2)) == Math.floor(Math.log(n) / Math.log(2)));
    }
 
    public static boolean canSumToPowerOfTwo(int n) {
        for (int i = 1; i < n; i++) {
            if (isPowerOfTwo(i) && isPowerOfTwo(n - i)) {
                return true;
            }
        }
        return false;
    }
 
    public static void main(String[] args) {
        int n = 10;
        if (canSumToPowerOfTwo(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Python3

import math
 
# Function to check if a number is a power of two
def isPowerOfTwo(n):
    if n == 0:
        return False
    return math.ceil(math.log2(n)) == math.floor(math.log2(n))
 
# Function to check if a number can be expressed as the sum of two powers of two
def canSumToPowerOfTwo(n):
    for i in range(1, n):
        if isPowerOfTwo(i) and isPowerOfTwo(n - i):
            return True
    return False
 
def main():
    n = 10
    if canSumToPowerOfTwo(n):
        print("Yes")
    else:
        print("No")
 
if __name__ == "__main__":
    main()

C#

using System;
 
class Program
{
    // Function to check if a number is a power of two
    static bool IsPowerOfTwo(int n)
    {
        // If the input number is 0, it cannot be a power of two
        if (n == 0)
        {
            return false;
        }
         
        // Calculate the logarithm base 2 of the input number
        double logValue = Math.Log(n, 2);
         
        // Check if the logarithm is an integer, which indicates it's a power of two
        return logValue == (int)logValue;
    }
 
    // Function to check if a number can be expressed as a sum of two powers of two
    static bool CanSumToPowerOfTwo(int n)
    {
        // Iterate through numbers from 1 to n-1
        for (int i = 1; i < n; i++)
        {
            // Check if both 'i' and 'n - i' are powers of two
            if (IsPowerOfTwo(i) && IsPowerOfTwo(n - i))
            {
                return true; // If such pair exists, return true
            }
        }
         
        return false; // If no pair of powers of two sums up to 'n', return false
    }
 
    static void Main(string[] args)
    {
        int n = 10; // Define the input number
         
        // Check if 'n' can be expressed as a sum of two powers of two
        if (CanSumToPowerOfTwo(n))
        {
            Console.WriteLine("Yes"); // Output "Yes" if it can
        }
        else
        {
            Console.WriteLine("No"); // Output "No" if it cannot
        }
    }
}

Javascript

// This function determines if a given integer n is a power of two
function isPowerOfTwo(n) {
    if (n == 0) {
        return false;
    }
    return (Math.ceil(Math.log2(n)) == Math.floor(Math.log2(n)));
}
 
// This function determines if it is possible to represent a given integer n
// as the sum of two distinct powers of two
function canSumToPowerOfTwo(n) {
 
    // Loop through all possible pairs of powers of two that sum to n
    for (let i = 1; i < n; i++) {
        if (isPowerOfTwo(i) && isPowerOfTwo(n-i)) {
            return true;
        }
    }
 
    // If no such pair exists, return false
    return false;
}
 
// Test the function with some sample input
let n = 10;
if (canSumToPowerOfTwo(n)) {
    console.log("Yes");
}
else {
    console.log("No");
}

Output:

Yes

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!