LeetCode 869: Reordered Power of 2
Problem Description
Explanation
To solve this problem, we can generate all possible permutations of the digits of the input number n, check if any of these permutations form a power of 2, and return true if we find one. We can use a helper function to check if a number is a power of 2 efficiently.
Algorithm:
- Convert the integer
nto a string to easily manipulate its digits. - Generate all permutations of the digits of
n. - For each permutation:
- Convert the permutation back to an integer.
- Check if the integer is a power of 2 using the helper function.
- If any permutation is a power of 2, return true. Otherwise, return false.
Time Complexity: O((log n)! * log n) where log n is the number of digits in n. Space Complexity: O(log n) for storing the permutations and recursive calls.
Solutions
class Solution {
public boolean reorderedPowerOf2(int n) {
String num = Integer.toString(n);
return permutationHelper(num.toCharArray(), 0);
}
private boolean permutationHelper(char[] arr, int index) {
if (index == arr.length) {
String numStr = new String(arr);
if (numStr.charAt(0) != '0' && isPowerOfTwo(Integer.parseInt(numStr))) {
return true;
}
}
for (int i = index; i < arr.length; i++) {
if (index == 0 && arr[i] == '0') continue;
swap(arr, index, i);
if (permutationHelper(arr, index + 1)) {
return true;
}
swap(arr, index, i);
}
return false;
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean isPowerOfTwo(int num) {
return num > 0 && (num & (num - 1)) == 0;
}
}Related LeetCode Problems
Loading editor...