Skip to main content

Check if permutation of number is power of 2 or not

The given problem is to check if any permutation of a given number is a power of 2. In other words, we need to find whether rearranging the digits of the number can form a power of 2 or not. For example, if the input number is 123, we need to check if any permutation of its digits (e.g., 231, 312, etc.) can form a power of 2.

Problem Statement

Given a positive integer 'num', we need to determine if any permutation of its digits can form a power of 2. If such a permutation exists, we need to find the power of 2; otherwise, we will state that no permutation of the number can be a power of 2.

Explanation with Example

Let's understand the problem with an example. Consider the number 76328.

Step 1: Check if any permutation of the digits can form a power of 2.

  • Permutations of 76328: 23867, 32678, 87632, 68237, 82376, 67823, etc.
  • None of these permutations are a power of 2, so we move to the next step.

Step 2: Check the permutations of each digit of the number.

  • Permutations of digit 7: 7
  • Permutations of digit 6: 6
  • Permutations of digit 3: 3
  • Permutations of digit 2: 2, 4, 8
  • Permutations of digit 8: 8
  • The permutation of the digit '2' forms the power of 2 (i.e., 2^5 = 32), so we stop here.

Output for 76328: Permutation 32768 is a power of 2.

Pseudocode

// Function to check if the digits of two numbers are the same
function isSameDigit(num, power)
    // Initialize two arrays to store digit frequencies
    array a[10], b[10]
    
    // Set initial frequency of all digits to 0
    for i = 0 to 9
        a[i] = 0
        b[i] = 0
        
    // Count digit frequency of num
    while num > 0
        digit = num % 10
        a[digit] = a[digit] + 1
        num = num / 10
    
    // Count digit frequency of power value
    while power > 0
        digit = power % 10
        b[digit] = b[digit] + 1
        power = power / 10
    
    // Compare frequency of both numbers
    for i = 0 to 9
        if a[i] != b[i]
            // When frequency is not the same
            return 0
            
    // Both numbers have the same digits
    return 1


// Function to check if any permutation of number is a power of 2
function isPowerof2(num)
    // Variable to store the result (power of 2)
    result = 0
    
    print "Given num:", num
    
    if num > 0
        // Check all powers of 2 in 32-bit integer
        for i = 0 to 30
            power = 1 << i
            if num == power or isSameDigit(num, power) == 1
                // Found a power of 2 with the same digits
                result = power
                break

    if result != 0
        print "Permutation", result, "is a power of 2"
    else
        print "No permutation of number", num, "is a power of 2"


// Test cases
isPowerof2(76328)
isPowerof2(1234)
isPowerof2(8240)
isPowerof2(23)
isPowerof2(21)
  1. Define a function to check if two numbers have the same digits (isSameDigit).
  2. Define a function to check if any permutation of the number is a power of 2 (isPowerof2).
  3. For each power of 2 (from 2^0 to 2^30), check if the given number or any permutation of it is a power of 2 using the isSameDigit function.
  4. Print the result accordingly.

Algorithm with Explanation

  1. Create a function called isSameDigit, which takes two integers 'num' and 'power' as input and returns 1 if both numbers have the same digits and 0 otherwise.
  2. In the isSameDigit function: a. Initialize two arrays, 'a' and 'b', of size 10 to store the frequency of digits from 0 to 9 for 'num' and 'power'. b. Initialize a loop variable 'i' from 0 to 9 and set both arrays 'a' and 'b' to 0. c. Calculate the frequency of each digit in 'num' and store it in the 'a' array. d. Calculate the frequency of each digit in 'power' and store it in the 'b' array. e. Compare the frequency of digits in both arrays 'a' and 'b', if any frequency is different, return 0 (not the same digits). f. If all frequencies are the same, return 1 (same digits).
  3. Create a function called isPowerof2, which takes an integer 'num' as input and prints whether any permutation of 'num' is a power of 2 or not.
  4. In the isPowerof2 function: a. Initialize a variable 'result' to store the power of 2 if found; otherwise, it remains 0. b. Check if 'num' is positive. If not, exit the function. c. Loop from 0 to 30 (as 2^31 will exceed the 32-bit integer range) and check if 'num' is equal to 2^i or if any permutation of 'num' is equal to 2^i using the isSameDigit function. d. If a power of 2 is found, set 'result' to 2^i and break the loop. e. After the loop, if 'result' is not 0, print that the permutation 'result' is a power of 2; otherwise, print that no permutation of 'num' is a power of 2.
  5. In the main function: a. Call the isPowerof2 function with different test cases: 76328, 1234, 8240, 23, and 21. b. The function will print the result for each test case.

Code Solution

Here given code implementation process.

// C program
// Check if permutation of number is power of 2 or not
#include <stdio.h>

// Check the both number have frequency is same or not
int isSameDigit(int num, int power)
{
	// Use to count number digit frequency
	// Digit [0 - 9]
	int a[10];
	int b[10];
	// Loop controlling variable
	int i = 0;
	// Set the initial frequency
	for (i = 0; i < 10; ++i)
	{
		a[i] = 0;
		b[i] = 0;
	}
	// Count digit frequency of num
	while (num > 0)
	{
		a[num % 10] += 1;
		// Remove last digit
		num = num / 10;
	}
	// Count digit frequency of power value
	while (power > 0)
	{
		b[power % 10]++;
		// Remove last digit
		power = power / 10;
	}
	// Compare frequency of both number
	for (i = 0; i < 10; ++i)
	{
		if (a[i] != b[i])
		{
			// When frequency are not same
			return 0;
		}
	}
	return 1;
}
void isPowerof2(int num)
{
	int result = 0;
	printf("\n Given num : %d", num);
	if (num > 0)
	{
		// Check all power of 2 in 32 bit integer
		for (int i = 0; i < 31 && result == 0; ++i)
		{
			if (num == (1 << i) || isSameDigit(num, 1 << i) == 1)
			{
				// Get resultant power
				result = (1 << i);
			}
		}
	}
	if (result != 0)
	{
		printf("\n Permutation %d is power of 2\n", result);
	}
	else
	{
		printf("\n No permutation of number %d is power of 2\n", num);
	}
}
int main(int argc, char
	const *argv[])
{
	// Test cases
	isPowerof2(76328);
	isPowerof2(1234);
	isPowerof2(8240);
	isPowerof2(23);
	isPowerof2(21);
	return 0;
}

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
// Java program for
// Check if permutation of number is power of 2 or not
public class PermutationPower
{
	// Check the both number have frequency is same or not
	public int isSameDigit(int num, int power)
	{
		// Use to count number digit frequency
		// Digit [0 - 9]
		int[] a = new int[10];
		int[] b = new int[10];
		// Loop controlling variable
		int i = 0;
		// Set the initial frequency
		for (i = 0; i < 10; ++i)
		{
			a[i] = 0;
			b[i] = 0;
		}
		// Count digit frequency of num
		while (num > 0)
		{
			a[num % 10] += 1;
			// Remove last digit
			num = num / 10;
		}
		// Count digit frequency of power value
		while (power > 0)
		{
			b[power % 10]++;
			// Remove last digit
			power = power / 10;
		}
		// Compare frequency of both number
		for (i = 0; i < 10; ++i)
		{
			if (a[i] != b[i])
			{
				// When frequency are not same
				return 0;
			}
		}
		return 1;
	}
	public void isPowerof2(int num)
	{
		int result = 0;
		System.out.print("\n Given num : " + num);
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			for (int i = 0; i < 31 && result == 0; ++i)
			{
				if (num == (1 << i) || isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
			}
		}
		if (result != 0)
		{
			System.out.print("\n Permutation " + result + " is power of 2\n");
		}
		else
		{
			System.out.print("\n No permutation of number " + num + " is power of 2\n");
		}
	}
	public static void main(String[] args)
	{
		PermutationPower task = new PermutationPower();
		// Test cases
		task.isPowerof2(76328);
		task.isPowerof2(1234);
		task.isPowerof2(8240);
		task.isPowerof2(23);
		task.isPowerof2(21);
	}
}

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Check if permutation of number is power of 2 or not

class PermutationPower
{
	public:
		// Check the both number have frequency is same or not
		int isSameDigit(int num, int power)
		{
			// Use to count number digit frequency
			// Digit [0 - 9]
			int a[10];
			int b[10];
			// Loop controlling variable
			int i = 0;
			// Set the initial frequency
			for (i = 0; i < 10; ++i)
			{
				a[i] = 0;
				b[i] = 0;
			}
			// Count digit frequency of num
			while (num > 0)
			{
				a[num % 10] += 1;
				// Remove last digit
				num = num / 10;
			}
			// Count digit frequency of power value
			while (power > 0)
			{
				b[power % 10]++;
				// Remove last digit
				power = power / 10;
			}
			// Compare frequency of both number
			for (i = 0; i < 10; ++i)
			{
				if (a[i] != b[i])
				{
					// When frequency are not same
					return 0;
				}
			}
			return 1;
		}
	void isPowerof2(int num)
	{
		int result = 0;
		cout << "\n Given num : " << num;
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			for (int i = 0; i < 31 && result == 0; ++i)
			{
				if (num == (1 << i) || this->isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
			}
		}
		if (result != 0)
		{
			cout << "\n Permutation " << result << " is power of 2\n";
		}
		else
		{
			cout << "\n No permutation of number " << num << " is power of 2\n";
		}
	}
};
int main()
{
	PermutationPower *task = new PermutationPower();
	// Test cases
	task->isPowerof2(76328);
	task->isPowerof2(1234);
	task->isPowerof2(8240);
	task->isPowerof2(23);
	task->isPowerof2(21);
	return 0;
}

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
// Include namespace system
using System;
// Csharp program for
// Check if permutation of number is power of 2 or not
public class PermutationPower
{
	// Check the both number have frequency is same or not
	public int isSameDigit(int num, int power)
	{
		// Use to count number digit frequency
		// Digit [0 - 9]
		int[] a = new int[10];
		int[] b = new int[10];
		// Loop controlling variable
		int i = 0;
		// Set the initial frequency
		for (i = 0; i < 10; ++i)
		{
			a[i] = 0;
			b[i] = 0;
		}
		// Count digit frequency of num
		while (num > 0)
		{
			a[num % 10] += 1;
			// Remove last digit
			num = num / 10;
		}
		// Count digit frequency of power value
		while (power > 0)
		{
			b[power % 10]++;
			// Remove last digit
			power = power / 10;
		}
		// Compare frequency of both number
		for (i = 0; i < 10; ++i)
		{
			if (a[i] != b[i])
			{
				// When frequency are not same
				return 0;
			}
		}
		return 1;
	}
	public void isPowerof2(int num)
	{
		int result = 0;
		Console.Write("\n Given num : " + num);
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			for (int i = 0; i < 31 && result == 0; ++i)
			{
				if (num == (1 << i) || this.isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
			}
		}
		if (result != 0)
		{
			Console.Write("\n Permutation " + result + " is power of 2\n");
		}
		else
		{
			Console.Write("\n No permutation of number " + num + " is power of 2\n");
		}
	}
	public static void Main(String[] args)
	{
		PermutationPower task = new PermutationPower();
		// Test cases
		task.isPowerof2(76328);
		task.isPowerof2(1234);
		task.isPowerof2(8240);
		task.isPowerof2(23);
		task.isPowerof2(21);
	}
}

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
<?php
// Php program for
// Check if permutation of number is power of 2 or not
class PermutationPower
{
	// Check the both number have frequency is same or not
	public	function isSameDigit($num, $power)
	{
		// Use to count number digit frequency
		// Digit [0 - 9]
		// Set the initial frequency
		$a = array_fill(0, 10, 0);
		$b = array_fill(0, 10, 0);
		// Loop controlling variable
		$i = 0;
		// Count digit frequency of num
		while ($num > 0)
		{
			$a[$num % 10] += 1;
			// Remove last digit
			$num = (int)($num / 10);
		}
		// Count digit frequency of power value
		while ($power > 0)
		{
			$b[$power % 10]++;
			// Remove last digit
			$power = (int)($power / 10);
		}
		// Compare frequency of both number
		for ($i = 0; $i < 10; ++$i)
		{
			if ($a[$i] != $b[$i])
			{
				// When frequency are not same
				return 0;
			}
		}
		return 1;
	}
	public	function isPowerof2($num)
	{
		$result = 0;
		echo("\n Given num : ".$num);
		if ($num > 0)
		{
			// Check all power of 2 in 32 bit integer
			for ($i = 0; $i < 31 && $result == 0; ++$i)
			{
				if ($num == (1 << $i) || $this->isSameDigit($num, 1 << $i) == 1)
				{
					// Get resultant power
					$result = (1 << $i);
				}
			}
		}
		if ($result != 0)
		{
			echo("\n Permutation ".$result.
				" is power of 2\n");
		}
		else
		{
			echo("\n No permutation of number ".$num.
				" is power of 2\n");
		}
	}
}

function main()
{
	$task = new PermutationPower();
	// Test cases
	$task->isPowerof2(76328);
	$task->isPowerof2(1234);
	$task->isPowerof2(8240);
	$task->isPowerof2(23);
	$task->isPowerof2(21);
}
main();

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
// Node JS program for
// Check if permutation of number is power of 2 or not
class PermutationPower
{
	// Check the both number have frequency is same or not
	isSameDigit(num, power)
	{
		// Use to count number digit frequency
		// Digit [0 - 9]
		// Set the initial frequency
		var a = Array(10).fill(0);
		var b = Array(10).fill(0);
		// Loop controlling variable
		var i = 0;
		// Count digit frequency of num
		while (num > 0)
		{
			a[num % 10] += 1;
			// Remove last digit
			num = parseInt(num / 10);
		}
		// Count digit frequency of power value
		while (power > 0)
		{
			b[power % 10]++;
			// Remove last digit
			power = parseInt(power / 10);
		}
		// Compare frequency of both number
		for (i = 0; i < 10; ++i)
		{
			if (a[i] != b[i])
			{
				// When frequency are not same
				return 0;
			}
		}
		return 1;
	}
	isPowerof2(num)
	{
		var result = 0;
		process.stdout.write("\n Given num : " + num);
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			for (var i = 0; i < 31 && result == 0; ++i)
			{
				if (num == (1 << i) || this.isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
			}
		}
		if (result != 0)
		{
			process.stdout.write("\n Permutation " + result + " is power of 2\n");
		}
		else
		{
			process.stdout.write("\n No permutation of number " + num + " is power of 2\n");
		}
	}
}

function main()
{
	var task = new PermutationPower();
	// Test cases
	task.isPowerof2(76328);
	task.isPowerof2(1234);
	task.isPowerof2(8240);
	task.isPowerof2(23);
	task.isPowerof2(21);
}
main();

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
#  Python 3 program for
#  Check if permutation of number is power of 2 or not
class PermutationPower :
	#  Check the both number have frequency is same or not
	def isSameDigit(self, num, power) :
		#  Use to count number digit frequency
		#  Digit [0 - 9]
		#  Set the initial frequency
		a = [0] * (10)
		b = [0] * (10)
		#  Loop controlling variable
		i = 0
		#  Count digit frequency of num
		while (num > 0) :
			a[num % 10] += 1
			#  Remove last digit
			num = int(num / 10)
		
		#  Count digit frequency of power value
		while (power > 0) :
			b[power % 10] += 1
			#  Remove last digit
			power = int(power / 10)
		
		#  Compare frequency of both number
		i = 0
		while (i < 10) :
			if (a[i] != b[i]) :
				#  When frequency are not same
				return 0
			
			i += 1
		
		return 1
	
	def isPowerof2(self, num) :
		result = 0
		print("\n Given num : ", num, end = "")
		if (num > 0) :
			#  Check all power of 2 in 32 bit integer
			i = 0
			while (i < 31 and result == 0) :
				if (num == (1 << i) or self.isSameDigit(num, 1 << i) == 1) :
					#  Get resultant power
					result = (1 << i)
				
				i += 1
			
		
		if (result != 0) :
			print("\n Permutation", result ,"is power of 2")
		else :
			print("\n No permutation of number", num ,"is power of 2")
		
	

def main() :
	task = PermutationPower()
	#  Test cases
	task.isPowerof2(76328)
	task.isPowerof2(1234)
	task.isPowerof2(8240)
	task.isPowerof2(23)
	task.isPowerof2(21)

if __name__ == "__main__": main()

input

 Given num :  76328
 Permutation 32768 is power of 2

 Given num :  1234
 No permutation of number 1234 is power of 2

 Given num :  8240
 Permutation 2048 is power of 2

 Given num :  23
 Permutation 32 is power of 2

 Given num :  21
 No permutation of number 21 is power of 2
#  Ruby program for
#  Check if permutation of number is power of 2 or not
class PermutationPower 
	#  Check the both number have frequency is same or not
	def isSameDigit(num, power) 
		#  Use to count number digit frequency
		#  Digit [0 - 9]
		#  Set the initial frequency
		a = Array.new(10) {0}
		b = Array.new(10) {0}
		#  Loop controlling variable
		i = 0
		#  Count digit frequency of num
		while (num > 0) 
			a[num % 10] += 1
			#  Remove last digit
			num = num / 10
		end

		#  Count digit frequency of power value
		while (power > 0) 
			b[power % 10] += 1
			#  Remove last digit
			power = power / 10
		end

		#  Compare frequency of both number
		i = 0
		while (i < 10) 
			if (a[i] != b[i]) 
				#  When frequency are not same
				return 0
			end

			i += 1
		end

		return 1
	end

	def isPowerof2(num) 
		result = 0
		print("\n Given num : ", num)
		if (num > 0) 
			#  Check all power of 2 in 32 bit integer
			i = 0
			while (i < 31 && result == 0) 
				if (num == (1 << i) || self.isSameDigit(num, 1 << i) == 1) 
					#  Get resultant power
					result = (1 << i)
				end

				i += 1
			end

		end

		if (result != 0) 
			print("\n Permutation ", result ," is power of 2\n")
		else 
			print("\n No permutation of number ", num ," is power of 2\n")
		end

	end

end

def main() 
	task = PermutationPower.new()
	#  Test cases
	task.isPowerof2(76328)
	task.isPowerof2(1234)
	task.isPowerof2(8240)
	task.isPowerof2(23)
	task.isPowerof2(21)
end

main()

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2

// Scala program for
// Check if permutation of number is power of 2 or not
class PermutationPower()
{
	// Check the both number have frequency is same or not
	def isSameDigit(n: Int, p: Int): Int = {
      	var num = n;
      	var power = p;
		// Use to count number digit frequency
		// Digit [0 - 9]
		// Set the initial frequency
		var a: Array[Int] = Array.fill[Int](10)(0);
		var b: Array[Int] = Array.fill[Int](10)(0);
		// Loop controlling variable
		var i: Int = 0;
		// Count digit frequency of num
		while (num > 0)
		{
			a(num % 10) += 1;
			// Remove last digit
			num = num / 10;
		}
		// Count digit frequency of power value
		while (power > 0)
		{
			b(power % 10) += 1;
			// Remove last digit
			power = power / 10;
		}
		// Compare frequency of both number
		while (i < 10)
		{
			if (a(i) != b(i))
			{
				// When frequency are not same
				return 0;
			}
			i += 1;
		}
		return 1;
	}
	def isPowerof2(num: Int): Unit = {
		var result: Int = 0;
		print("\n Given num : " + num);
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			var i: Int = 0;
			while (i < 31 && result == 0)
			{
				if (num == (1 << i) || isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
				i += 1;
			}
		}
		if (result != 0)
		{
			print("\n Permutation " + result + " is power of 2\n");
		}
		else
		{
			print("\n No permutation of number " + num + " is power of 2\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: PermutationPower = new PermutationPower();
		// Test cases
		task.isPowerof2(76328);
		task.isPowerof2(1234);
		task.isPowerof2(8240);
		task.isPowerof2(23);
		task.isPowerof2(21);
	}
}

input

 Given num : 76328
 Permutation 32768 is power of 2

 Given num : 1234
 No permutation of number 1234 is power of 2

 Given num : 8240
 Permutation 2048 is power of 2

 Given num : 23
 Permutation 32 is power of 2

 Given num : 21
 No permutation of number 21 is power of 2
// Swift 4 program for
// Check if permutation of number is power of 2 or not
class PermutationPower
{
	// Check the both number have frequency is same or not
	func isSameDigit(_ n: Int, _ p: Int) -> Int
	{
      	var num = n;
      	var power = p;
		// Use to count number digit frequency
		// Digit [0 - 9]
		// Set the initial frequency
		var a: [Int] = Array(repeating: 0, count: 10);
		var b: [Int] = Array(repeating: 0, count: 10);
		// Loop controlling variable
		var i: Int = 0;
		// Count digit frequency of num
		while (num > 0)
		{
			a[num % 10] += 1;
			// Remove last digit
			num = num / 10;
		}
		// Count digit frequency of power value
		while (power > 0)
		{
			b[power % 10] += 1;
			// Remove last digit
			power = power / 10;
		}
		// Compare frequency of both number
		i = 0;
		while (i < 10)
		{
			if (a[i] != b[i])
			{
				// When frequency are not same
				return 0;
			}
			i += 1;
		}
		return 1;
	}
	func isPowerof2(_ num: Int)
	{
		var result: Int = 0;
		print("\n Given num : ", num, terminator: "");
		if (num > 0)
		{
			// Check all power of 2 in 32 bit integer
			var i: Int = 0;
			while (i < 31 && result == 0)
			{
				if (num == (1 << i) || self.isSameDigit(num, 1 << i) == 1)
				{
					// Get resultant power
					result = (1 << i);
				}
				i += 1;
			}
		}
		if (result != 0)
		{
			print("\n Permutation ", result ," is power of 2");
		}
		else
		{
			print("\n No permutation of number ", num ," is power of 2");
		}
	}
}
func main()
{
	let task: PermutationPower = PermutationPower();
	// Test cases
	task.isPowerof2(76328);
	task.isPowerof2(1234);
	task.isPowerof2(8240);
	task.isPowerof2(23);
	task.isPowerof2(21);
}
main();

input

 Given num :  76328
 Permutation  32768  is power of 2

 Given num :  1234
 No permutation of number  1234  is power of 2

 Given num :  8240
 Permutation  2048  is power of 2

 Given num :  23
 Permutation  32  is power of 2

 Given num :  21
 No permutation of number  21  is power of 2

Resultant Output Explanation

  • For the given test cases: 76328, 1234, 8240, 23, and 21, the program will check if any permutation of the numbers is a power of 2.
  • The output will state whether any permutation is a power of 2 and, if so, which power of 2 it is.
  • For example, for the input '76328', the output will be 'Permutation 32768 is a power of 2', as the permutation '32768' is a power of 2 (2^15 = 32768).
  • For the input '1234', the output will be 'No permutation of number 1234 is a power of 2', as none of the permutations of '1234' form a power of 2.

Time Complexity of Code

The time complexity of the provided code mainly depends on two parts: the isSameDigit function and the isPowerof2 function.

  1. isSameDigit Function:

    • The function iterates through the digits of 'num' and 'power', which takes O(log n) time, where 'n' is the maximum of 'num' and 'power'.
    • The comparison of the frequencies of digits in arrays 'a' and 'b' takes constant time, O(1), as there are a fixed number of digits (10).
    • Overall, the time complexity of the isSameDigit function is O(log n), where 'n' is the maximum of 'num' and 'power'.

  2. isPowerof2 Function:

    • The function iterates from 0 to 30 (fixed number of iterations), so the loop takes constant time, O(1).
    • Inside the loop, the isSameDigit function is called for each iteration, which takes O(log n) time, where 'n' is the maximum of 'num' and 'power'.
    • Overall, the time complexity of the isPowerof2 function is O(1) * O(log n) = O(log n), where 'n' is the maximum of 'num' and the largest power of 2 (2^30).

  3. Main Function:

    • The main function calls the isPowerof2 function for each test case, so the time complexity of the main function depends on the number of test cases.
    • If there are 'k' test cases, the overall time complexity of the main function is O(k * log n), where 'n' is the maximum number in the test cases.

In conclusion, the overall time complexity of the given code is O(k * log n), where 'n' is the maximum number in the test cases and 'k' is the number of test cases. As the maximum value of 'n

Last updated on by Kalkicode




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