Reordered Power of 2 - Medium Difficulty

-
Hello dear friends, problem is this one: https://leetcode.com/problems/reordered-power-of-2/description/

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!!! Boris


    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

    1. TarasSeptember 3, 2019 at 3:13 PM

      This problem reminds me search for anagrams a little:

      class 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;
      }
      };

      ReplyDelete

    Post a Comment

    Popular posts from this blog

    Count Binary Substrings

    -
    Image
    Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
    Read more

    Count Vowels Permutation: Standard DP

    -
    Image
    Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
    Read more

    Maximum Number of Balloons

    -
    Image
    #431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
    Read more