✅Reordered Power of 2 | Short & Easy w/ Explanation | Beats 100%
Solution - I (Counting Digits Frequency)\n\nA simple solution is to check if frequency of digits in N and all powers of 2 less than 10^9 are equal. In our case,
***Solution - I (Counting Digits Frequency)***\n\nA simple solution is to check if frequency of digits in N and all powers of 2 less than `10^9` are equal. In our case, we need to check for all powers of 2 from `2^0` to `2^29` and if any of them matches with digits in `N`, return true.\n\n```\n// counts frequency of each digit in given number N and returns it as vector\nvector<int> countDigits(int N){\n\tvector<int>digitsInN(10);\n\twhile(N)\n\t\tdigitsInN[N % 10]++, N /= 10;\n\treturn digitsInN;\n}\nbool reorderedPowerOf2(int N) {\n\tvector<int> digitsInN = countDigits(N); // freq of digits in N\n\t// powOf2 goes from 2^0 to 2^29 and each time freq of digits in powOf2 is compared with digitsInN\n\tfor(int i = 0, powOf2 = 1; i < 30; i++, powOf2 <<= 1)\n\t\tif(digitsInN == countDigits(powOf2)) return true;  // return true if both have same frequency of each digits\n\treturn false;\n}\n```\n\n**Time Complexity :** **`O(logn)`**, where `n` is maximum power of 2 for which digits are counted (2^30). More specifically the time complexity can be written as `O(logN + log2 + log4 + ... + log(2^30))` which after ignoring the constant factors and lower order terms comes out to `O(logn)`.\n**Time Complexity :** **`O(1)`**. We are using vector to store digits of `N` and powers of 2 but they are taking constant space and don\'t depend on the input `N`.\n\n---------\n---------\n\n***Solution - II (Convert to string & sort)***\n\nWe can convert `N` to string, sort it and compare it with every power of 2 by converting and sorting that as well.\n\n```\nbool reorderedPowerOf2(int N) {\n\tstring n = to_string(N);\n\tsort(begin(n), end(n));\n\tfor(int i = 0, powOf2 = 1; i < 30; i++, powOf2 <<= 1){\n\t\tstring pow2_str = to_string(powOf2);\n\t\tsort(begin(pow2_str), end(pow2_str));\n\t\tif(n == pow2_str) return true;  \n\t}\n\treturn false;\n}\n```\n\n-------\n\nBoth solutions have the same run-time -\n\n![image](https://assets.leetcode.com/users/images/ec72eb4f-071d-4c4f-91b1-c6c098015f29_1616318669.6588662.png)\n\n-------\n-------
['C']