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. 20 cannot contribute to the sum.
Examples:
Input: N = 10
Output: 1
23 + 21 = 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 20 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^0bool isSumOfPowersOfTwo(int n){ if (n % 2 == 1) return false; else return true;}// Driver codeint main(){ int n = 10; if (isSumOfPowersOfTwo(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass 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^0def isSumOfPowersOfTwo(n): if n % 2 == 1: return False else: return True# Driver coden = 10if isSumOfPowersOfTwo(n): print("Yes")else: print("No")# This code is contributed# by Shrikant13 |
C#
// C# implementation of the approachusing 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^0function isSumOfPowersOfTwo(n){ if (n % 2 == 1) return false; else return true;}// Driver codevar 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^0function 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 twodef 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 twodef canSumToPowerOfTwo(n): for i in range(1, n): if isPowerOfTwo(i) and isPowerOfTwo(n - i): return True return Falsedef 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 twofunction 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 twofunction 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 inputlet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
