Reordered Power of 2 - Medium Difficulty
Hello dear friends, problem is this one: https://leetcode.com/problems/reordered-power-of-2/description/
This is a medium-difficulty problem, but if you pay close attention to the constraints you can solve it relatively easy.
First, the upper limit is really small: 10^9.
The approach that can be taken is to use a static hashtable (static so that you don't have to recompute it all the time) holding all the powers of two between 0 and 10^9.
There won't be many since they grow exponentially fast.
But you don't want to just store the powers of two as they are in the hashtable. What you want is to store each number in a canonical manner.
One way to do so is to sort the digits in that number.
If you're going to sort digits in a number, don't use QSort or MSort, rather, use bucket sort (linear).
Now that you have all the powers of two in a canonical format in a hashtable, just sort the input and compare to the elements in the hashtable.
Runs super fast.
Many hugs!!! Marcelo
public class Solution
{
private static Hashtable powerOf2Sorted = null;
public bool ReorderedPowerOf2(int N)
{
if (Solution.powerOf2Sorted == null)
{
Solution.powerOf2Sorted = new Hashtable();
for (long i = 1; i <= 1000000000; i *= 2)
Solution.powerOf2Sorted.Add(Sort(i), true);
}
return powerOf2Sorted.ContainsKey(Sort(N));
}
private string Sort(long N)
{
long[] bucket = new long[10];
while (N > 0)
{
bucket[N % 10]++;
N /= 10;
}
string str = "";
for (int i = bucket.Length - 1; i >= 0; i--)
{
for (int j = 0; j < bucket[i]; j++)
{
str += i.ToString();
}
}
return str;
}
}
Starting with a positive 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 in a way such that the resulting number is a power of 2.
Example 1:
Input: 1 Output: true
Example 2:
Input: 10 Output: false
Example 3:
Input: 16 Output: true
Example 4:
Input: 24 Output: false
Example 5:
Input: 46 Output: true
This is a medium-difficulty problem, but if you pay close attention to the constraints you can solve it relatively easy.
First, the upper limit is really small: 10^9.
The approach that can be taken is to use a static hashtable (static so that you don't have to recompute it all the time) holding all the powers of two between 0 and 10^9.
There won't be many since they grow exponentially fast.
But you don't want to just store the powers of two as they are in the hashtable. What you want is to store each number in a canonical manner.
One way to do so is to sort the digits in that number.
If you're going to sort digits in a number, don't use QSort or MSort, rather, use bucket sort (linear).
Now that you have all the powers of two in a canonical format in a hashtable, just sort the input and compare to the elements in the hashtable.
Runs super fast.
Many hugs!!! Marcelo
public class Solution
{
private static Hashtable powerOf2Sorted = null;
public bool ReorderedPowerOf2(int N)
{
if (Solution.powerOf2Sorted == null)
{
Solution.powerOf2Sorted = new Hashtable();
for (long i = 1; i <= 1000000000; i *= 2)
Solution.powerOf2Sorted.Add(Sort(i), true);
}
return powerOf2Sorted.ContainsKey(Sort(N));
}
private string Sort(long N)
{
long[] bucket = new long[10];
while (N > 0)
{
bucket[N % 10]++;
N /= 10;
}
string str = "";
for (int i = bucket.Length - 1; i >= 0; i--)
{
for (int j = 0; j < bucket[i]; j++)
{
str += i.ToString();
}
}
return str;
}
}
Comments
This problem reminds me search for anagrams a little:
Reply Deleteclass Solution {
public:
bool reorderedPowerOf2(int N) {
string needle = to_string(N);
sort(needle.begin(), needle.end());
for (int p = 0; p < 32; ++p) {
string candidate = to_string(1 << p);
sort(candidate.begin(), candidate.end());
if (needle == candidate) return true;
}
return false;
}
};
Post a Comment
[γγ¬γΌγ ]