Sponsored
Sponsored
One approach to solve the problem is to leverage the fact that two numbers with the same digits in different orders will have the same digit frequency (or count of each digit). For the given number n, we aim to check if its digits can be rearranged to form any power of two. To achieve this:
10^9 and store their digit frequency in a set.n, calculate its digit frequency and check if it exists in the set.Time Complexity: O(1) because the number of power of twos checked (31) and the frequency array size (10) are constant.
Space Complexity: O(1) as only small fixed-size integer arrays are used.
1function reorderedPowerOf2(n) {
2 const countDigits = (num) => Array.from(num.toString()).sort().join('');
3 const nDigits = countDigits(n);
4 for (let i = 0; i < 31; i++) {
5 if (nDigits === countDigits(1 << i)) {
6 return true;
7 }
8 }
9 return false;
10}
11
12console.log(reorderedPowerOf2(1)); // Output: trueIn JavaScript, digit characters of n are sorted and concatenated into a string. The function then checks if this string is identical to sorted digit strings of any powers of two, indicating permutations.
A backtracking method can be employed by generating permutations of the digits of the number n and checking if any results in a power of two. Given the constraint, this method needs optimization to efficiently discard invalid permutations early.
n's digits where the leading digit isn't zero.Not provided due to complexity constraints in inline format.
1using System.Linq;
using System.Collections.Generic;
public class Solution {
public bool ReorderedPowerOf2(int n) {
string nStr = n.ToString();
var digits = nStr.ToArray();
return Permute(digits, 0).Any(num => IsPowerOf2(num));
}
private bool IsPowerOf2(int num) {
return (num & (num - 1)) == 0;
}
public IEnumerable<int> Permute(char[] digits, int start) {
if (start == digits.Length - 1) {
yield return int.Parse(new string(digits));
}
else
{
for (int i = start; i < digits.Length; i++) {
Swap(digits, start, i);
foreach (var num in Permute(digits, start + 1)) {
if (num.ToString()[0] != '0') yield return num;
}
Swap(digits, start, i);
}
}
}
private void Swap(char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.ReorderedPowerOf2(10)); // Output: False
}
}The C# approach involves recursive permutation generation with yield return to create states dynamically, checking against power of two alongside.