Skip to main content

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

  1. Start by defining the powerOf2 function that takes an integer parameter num.
  2. Initialize a variable count to 0. This variable will be used to keep track of the power of 2.
  3. Display the input number using the printf function.
  4. Display "Power 2 :" to indicate that the following numbers are powers of 2.
  5. 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.
  6. If the condition is true, print the current power of 2 using the printf function.
  7. Increment the count by 1 to move to the next power of 2.
  8. Repeat steps 5 to 7 until the condition (2^count <= num) becomes false.
  9. 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.

  1. 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.

  2. 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.

  3. 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.

  4. 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).





Comment

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