Problem

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Examples

Example 1:

1
2

Input: n = 1
Output: true

Example 2:

1
2

Input: n = 10
Output: false

Constraints

  • 1 <= n <= 109

Solution

Method 1 - Generate Powers of Two and Compare Anagrams

We know power of 2:

1
2
3
4
5
6
7
8
9

1   -> 1
2   -> 10
4   -> 100
8   -> 1000
16  -> 10000
64  -> 100000
128 -> 1000000
256 -> 10000000
...

Consider the input number 46. The answer should be true because 64 is a power of 2. Generating all permutations of 46 is time-consuming.

Instead, we can generate and sort the digits of powers of 2, for example, 64 remains 64, and 1024 becomes 4210 when sorted. When given an input number like 46, we can sort its digits to get 64, which matches a power of 2.

To generate powers of 2, we can use the left shift operator, continuing until the value exceeds the constraint of 10^9.

This problem in a way is similar to Group Anagrams.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public boolean reorderedPowerOf2(int N) {
	String s1 = transform(N);
	
	for (int i = 0; i < 31; i++) {
		int powerOfTwo = (int)(1 << i);
		String s2 = transform(powerOfTwo);
		if (s1.equals(s2)) {
			return true;
		}
	}
	
	return false;
}
private String transform(int num) {
	char[] a1 = String.valueOf(num).toCharArray();
	Arrays.sort(a1);
	return new String(a1);
}

Complexity

  • Time: O(m log m), where m is number of digits
    • Transform method takes O(m)
    • And we call transform method log m time
  • Space: O(m)

Method 2 - Generate Power of Twos and Compare Digits

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public boolean reorderedPowerOf2(int n) {
	char[] number = sortedDigits(n);

	for (int i = 0; i < 30; ++i) {
		char[] powerOfTwo = sortedDigits(1<< i);
		if (Arrays.equals(number, powerOfTwo)) {
			return true;		
		}
	}
	return false;
}

private char[] sortedDigits(int n) {
	char[] digits = String.valueOf(n).toCharArray();
	Arrays.sort(digits);
	return digits;
}

Method 3 - Generate Power of Twos and Compare Digit Frequency

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public boolean reorderedPowerOf2(int N) {
	int[] inputDigitFrequency = getDigitFrequency(N);
	for (int i = 0; i<31; i++) {
		int twoToPowerOfI = (int) Math.pow(2, i);
		int[] powerOf2FreqCount = getDigitFrequency(twoToPowerOfI);
		if (compareArray(inputDigitFrequency, powerOf2FreqCount)) {
			return true;
		}

	}
	return false;
}

private int[] getDigitFrequency(int n) {
	int[] digitFreq = new int[10];
	while (n > 0) {
		digitFreq[n % 10]++;
		n = n / 10;
	}
	return digitFreq;
}

private boolean compareArray(int[] freqCount1, int[] freqCount2) {
	for (int i = 0; i<10; i++) {
		if (freqCount1[i] != freqCount2[i]) {
			return false;
		}
	}
	return true;
}

Complexity

  • Time: O(NNNXXXNNN)
  • Space: O(NNNXXX)