Given a positive number N, the task is to find out all the perfect powers of two which are less than or equal to the given number N.
Examples:
Input: N = 63
Output: 32 16 8 4 2 1
Explanation: There are total of 6 powers of 2, which are less than or equal to the given number N.Input: N = 193
Output: 128 64 32 16 8 4 2 1
Explanation: There are total of 8 powers of 2, which are less than or equal to the given number N.
Naive Approach: The idea is to traverse each number from N to 1 and check if it is a perfect power of 2 or not. If yes, then print that number.
Another Approach: The idea is to find all powers of 2 and simply print the powers that are lesser than or equal to N.
Another Approach: The idea is based on the concept that all powers of 2 has all bits set, in its binary form. Bitset function is used in this approach solve the above problem.
Below are the steps:
- Find the largest power of 2(say temp) which is used to evaluate the number less than or equal to N.
- Initialise an bitset array arr[] of maximum size 64, to store the binary representation of the given number N.
- Reset all the bits in the bitset array using reset() function.
- Iterate a loop from total to 0, and sequentially make each bit 1, and find the value of that binary expression and then reset the bit.
Below is the implementation of the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAX = 64;// Function to return max exponent of// 2 which evaluates a number less// than or equal to Nint max_exponent(int n){ return (int)(log2(n));}// Function to print all the powers// of 2 less than or equal to Nvoid all_powers(int N){ bitset<64> arr(N); // Reset all the bits arr.reset(); int total = max_exponent(N); // Iterate from total to 0 for (int i = total; i >= 0; i--) { // Reset the next bit arr.reset(i + 1); // Set the current bit arr.set(i); // Value of the binary expression cout << arr.to_ulong() << " "; }}// Driver Codeint main(){ // Given Number int N = 63; // Function Call all_powers(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to return max exponent of // 2 which evaluates a number less // than or equal to N static int max_exponent(int n) { return (int)(Math.log(n) / Math.log(2)); } // Function to print all the powers // of 2 less than or equal to N static void all_powers(int N) { int total = max_exponent(N); // Reset all the bits char[] arr = new char[total + 2]; for (int i = 0; i <= total + 1; i++) arr[i] = '0'; // Iterate from total to 0 for (int i = 1; i < total + 2; i++) { // Reset the next bit arr[i - 1] = '0'; // Set the current bit arr[i] = '1'; // Value of the binary expression System.out.print( Integer.parseInt(new String(arr), 2) + " "); } System.out.print("\n"); } // Driver Code public static void main(String[] args) { // Given Number int N = 63; // Function Call all_powers(N); }}// This code is contributed by phasing17. |
Python3
# Python3 program for the above approachfrom math import log MAX = 64;# Function to return max exponent of# 2 which evaluates a number less# than or equal to Ndef max_exponent(n): return int(log(n,2))# Function to print all the powers# of 2 less than or equal to Ndef all_powers(N): total = max_exponent(N); # Reset all the bits arr = ['0' for _ in range(total + 2)] # Iterate from total to 0 for i in range(1, total + 2): # Reset the next bit arr[i - 1] = '0'; # Set the current bit arr[i] = '1'; # Value of the binary expression print( int("".join(arr), 2), end = " ") print() # Driver Code# Given NumberN = 63;# Function Callall_powers(N)# This code is contributed by phasing17. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to return max exponent of // 2 which evaluates a number less // than or equal to N static int max_exponent(int n) { return (int)(Math.Log(n) / Math.Log(2)); } // Function to print all the powers // of 2 less than or equal to N static void all_powers(int N) { int total = max_exponent(N); // Reset all the bits char[] arr = new char[total + 2]; for (int i = 0; i <= total + 1; i++) arr[i] = '0'; // Iterate from total to 0 for (int i = 1; i < total + 2; i++) { // Reset the next bit arr[i - 1] = '0'; // Set the current bit arr[i] = '1'; // Value of the binary expression Console.Write(Convert.ToInt32(new string(arr), 2) + " "); } Console.Write("\n"); } // Driver Code public static void Main(string[] args) { // Given Number int N = 63; // Function Call all_powers(N); }}// This code is contributed by phasing17. |
Javascript
// JS program for the above approachlet MAX = 64;// Function to return max exponent of// 2 which evaluates a number less// than or equal to Nfunction max_exponent(n){ return Math.floor(Math.log(n) / Math.log(2))}// Function to print all the powers// of 2 less than or equal to Nfunction all_powers(N){ let total = max_exponent(N); let arr = new Array(total + 1); // Reset all the bits arr.fill(0) // Iterate from total to 0 for (var i = total; i >= 0; i--) { // Reset the next bit arr[i + 1] = 0; // Set the current bit arr[i] = 1; // Value of the binary expression process.stdout.write( parseInt(arr.join(""), 2)/2 + " "); }}// Driver Code// Given Numberlet N = 63;// Function Callall_powers(N);// This code is contributed by phasing17. |
Output:
32 16 8 4 2 1
Time Complexity: O(log N)
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!
