# 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, b

// 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;
int b;
// 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;
int[] b = new int;
// 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)
{
// Test cases
}
}``````

#### 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;
int b;
// 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()
{
// Test cases
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;
int[] b = new int;
// 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)
{
// Test cases
}
}``````

#### 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()
{
// Test cases
}
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()
{
// Test cases
}
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 =  * (10)
b =  * (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() :
#  Test cases

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()
#  Test cases
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
}
}``````

#### 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()
{
// Test cases
}
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

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