Find all powers of 2 less than or equal to a given number
The given problem is to find all powers of 2 that are less than or equal to a given number. A power of 2 is a number of the form 2^n, where n is a non-negative integer. The task is to identify all such powers of 2 that are less than or equal to the given input number and then display them.
Explanation with Suitable Example
Let's take an example to understand the problem better. Consider the input number as 25. We need to find all powers of 2 that are less than or equal to 25. The powers of 2 less than or equal to 25 are 1, 2, 4, 8, and 16. These numbers are 2^0, 2^1, 2^2, 2^3, and 2^4 respectively.
Standard Pseudocode
The pseudocode for this problem can be written as follows:
function powerOf2(num):
count = 0
display "Number : num"
display "Power 2 :"
while (2^count <= num):
display 2^count
count++
Algorithm with Proper Explanation
- Start by defining the
powerOf2
function that takes an integer parameternum
. - Initialize a variable
count
to 0. This variable will be used to keep track of the power of 2. - Display the input number using the
printf
function. - Display "Power 2 :" to indicate that the following numbers are powers of 2.
- Enter a while loop, where the condition checks if the current power of 2 (2^count) is less than or equal to the
input number
num
. - If the condition is true, print the current power of 2 using the
printf
function. - Increment the
count
by 1 to move to the next power of 2. - Repeat steps 5 to 7 until the condition (2^count <= num) becomes false.
- The function will terminate, and all the powers of 2 less than or equal to the given number will be displayed.
Code Solution
Here given code implementation process.
// C program
// Find all powers of 2 less than or equal to a given number
#include <stdio.h>
// Find all power of two which is less than or equal to given number
void powerOf2(int num)
{
int count = 0;
// Display given numbers
printf("\n Number : %d", num);
printf("\n Power 2 : ");
while ((1 << count) <= num)
{
printf(" %d", 1 << count);
// Change bit position
count++;
}
}
int main(int argc, char
const *argv[])
{
// Test Cases
powerOf2(10);
powerOf2(40);
powerOf2(64);
powerOf2(43);
return 0;
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
/*
Java program
Find all powers of 2 less than or equal to a given number
*/
public class Power
{
// Find all power of two which is less than or equal to given number
public void powerOf2(int num)
{
int count = 0;
// Display given numbers
System.out.print("\n Number : " + num );
System.out.print("\n Power 2 : ");
while ((1 << count) <= num)
{
System.out.print(" " + (1 << count) );
// Change bit position
count++;
}
}
public static void main(String[] args)
{
Power task = new Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
public:
// Find all power of two which is less than or equal to given number
void powerOf2(int num)
{
int count = 0;
// Display given numbers
cout << "\n Number : " << num;
cout << "\n Power 2 : ";
while ((1 << count) <= num)
{
// Change bit position
cout << " " << (1 << count);
count++;
}
}
};
int main()
{
Power task = Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
return 0;
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
// Include namespace system
using System;
/*
C# program
Find all powers of 2 less than or equal to a given number
*/
public class Power
{
// Find all power of two which is less than or equal to given number
public void powerOf2(int num)
{
int count = 0;
// Display given numbers
Console.Write("\n Number : " + num);
Console.Write("\n Power 2 : ");
while ((1 << count) <= num)
{
// Change bit position
Console.Write(" " + (1 << count));
count++;
}
}
public static void Main(String[] args)
{
Power task = new Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
<?php
/*
Php program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
// Find all power of two which is less than or equal to given number
public function powerOf2($num)
{
$count = 0;
// Display given numbers
echo "\n Number : ". $num;
echo "\n Power 2 : ";
while ((1 << $count) <= $num)
{
// Change bit position
echo " ". (1 << $count);
$count++;
}
}
}
function main()
{
$task = new Power();
// Test Cases
$task->powerOf2(10);
$task->powerOf2(40);
$task->powerOf2(64);
$task->powerOf2(43);
}
main();
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
/*
Node Js program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
// Find all power of two which is less than or equal to given number
powerOf2(num)
{
var count = 0;
// Display given numbers
process.stdout.write("\n Number : " + num);
process.stdout.write("\n Power 2 : ");
while ((1 << count) <= num)
{
// Change bit position
process.stdout.write(" " + (1 << count));
count++;
}
}
}
function main()
{
var task = new Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
main();
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
# Python 3 program
# Find all powers of 2 less than or equal to a given number
class Power :
# Find all power of two which is less than or equal to given number
def powerOf2(self, num) :
count = 0
# Display given numbers
print("\n Number : ", num, end = "")
print("\n Power 2 : ", end = "")
while ((1 << count) <= num) :
print(" ", (1 << count), end = "")
# Change bit position
count += 1
def main() :
task = Power()
# Test Cases
task.powerOf2(10)
task.powerOf2(40)
task.powerOf2(64)
task.powerOf2(43)
if __name__ == "__main__": main()
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
# Ruby program
# Find all powers of 2 less than or equal to a given number
class Power
# Find all power of two which is less than or equal to given number
def powerOf2(num)
count = 0
# Display given numbers
print("\n Number : ", num)
print("\n Power 2 : ")
while ((1 << count) <= num)
print(" ", (1 << count))
# Change bit position
count += 1
end
end
end
def main()
task = Power.new()
# Test Cases
task.powerOf2(10)
task.powerOf2(40)
task.powerOf2(64)
task.powerOf2(43)
end
main()
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
/*
Scala program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
// Find all power of two which is less than or equal to given number
def powerOf2(num: Int): Unit = {
var count: Int = 0;
// Display given numbers
print("\n Number : " + num);
print("\n Power 2 : ");
while ((1 << count) <= num)
{
// Change bit position
print(" " + (1 << count));
count += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Power = new Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
/*
Swift 4 program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
// Find all power of two which is less than or equal to given number
func powerOf2(_ num: Int)
{
var count: Int = 0;
// Display given numbers
print("\n Number : ", num, terminator: "");
print("\n Power 2 : ", terminator: "");
while ((1 << count) <= num)
{
// Change bit position
print(" ", (1 << count), terminator: "");
count += 1;
}
}
}
func main()
{
let task: Power = Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
main();
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
/*
Kotlin program
Find all powers of 2 less than or equal to a given number
*/
class Power
{
// Find all power of two which is less than or equal to given number
fun powerOf2(num: Int): Unit
{
var count: Int = 0;
// Display given numbers
print("\n Number : " + num);
print("\n Power 2 : ");
while ((1 shl count) <= num)
{
// Change bit position
print(" " + (1 shl count));
count += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Power = Power();
// Test Cases
task.powerOf2(10);
task.powerOf2(40);
task.powerOf2(64);
task.powerOf2(43);
}
Output
Number : 10
Power 2 : 1 2 4 8
Number : 40
Power 2 : 1 2 4 8 16 32
Number : 64
Power 2 : 1 2 4 8 16 32 64
Number : 43
Power 2 : 1 2 4 8 16 32
Resultant Output Explanation
Let's see the output of the provided C code with the given test cases.
-
powerOf2(10) Number : 10 Power 2 : 1 2 4 8
The powers of 2 less than or equal to 10 are 1, 2, 4, and 8.
-
powerOf2(40) Number : 40 Power 2 : 1 2 4 8 16 32
The powers of 2 less than or equal to 40 are 1, 2, 4, 8, 16, and 32.
-
powerOf2(64) Number : 64 Power 2 : 1 2 4 8 16 32 64
The powers of 2 less than or equal to 64 are 1, 2, 4, 8, 16, 32, and 64.
-
powerOf2(43) Number : 43 Power 2 : 1 2 4 8 16 32
The powers of 2 less than or equal to 43 are 1, 2, 4, 8, 16, and 32.
Time Complexity:
The time complexity of this code is O(log N), where N is the input number. In the while loop, we keep doubling the
power of 2 (1, 2, 4, 8, ...) until it reaches or exceeds the given number num
. Since each iteration
effectively doubles the value, the number of iterations required is logarithmic to the input num
.
Hence, the time complexity is O(log N).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment