Understanding Reordered Power of 2 in 3 Basic Steps
I broke it down into 3 core parts:\n1. Identify individual digits of the number\n2. Identify valid permutations of the digits\n3. Test to see if a permutation i
I broke it down into 3 core parts:\n1. Identify individual digits of the number\n2. Identify valid permutations of the digits\n3. Test to see if a permutation is a power of 2.\n\n**Step 1:  Identify the Digits**\nIf I as a human see the number 1,024, I\'ll list the digits from left-to-right:  1, 0, 2, 4.  But if I want a computer to do it, I\'m better off going from right-to-left:  4, 2, 0, 1.  How can we make the computer do this?  How can we ask it to tell us, "What\'s in the 1\'s column?"\n\n1. Divide the number by 10:  `1024 / 10 = 102`\n2. Multiply by it by 10:  `102 * 10 = 1020`\n3. Subtract this result from the original value:  `1024 - 1020 = 4`\n\nJust divide the original number by 10 and repeat the process until you run out of digits!\n\n**Step 2:  Identify Valid Permutations**\nHow many different ways can we arrange these digits, and what are they?  Well, do we actually care?  We don\'t really need to *enumerate* the permutations, we just need to *identify* them.  That\'s a boolean test.  If I ask you, "Is 4210 a permutation of the digits in 1024?" how do you answer that question?  If you\'re like me, you just check to see if all digits have been used. \n\nYou can use an integer array of length 10 to count the digits in the input number.  For each digit observed in step 1, increment the corresponding index in the array.  Using 1024 (or 4210!) as our example, the resulting array should be:  `[1, 1, 1, 0, 1, 0, 0, 0, 0, 0]`\n\nIf our input number was `55,963,220`, the array would be:   `[1, 0, 2, 1, 0, 2, 1, 0, 0, 1]`\n\nIf two numbers\' arrays are equal, then the digits of one number can be rearranged to make the other!\n\n**Step 3: Test Powers of 2**\nWho remembers their big O times?  What grows faster:  `O(x^2)`, or `O(2^x)`?  The anwer is the latter. `2^x` grows pretty quickly.  In fact, `2^30 == 1,073,741,824`, and that\'s greater than a billion.  The problem statement says that n will be less than 10 to the 9th, which means we only have 30 dfferent powers of 2 that we\'d need to test.  That\'s a pretty small data set to test!  Just generate powers of 2, and extract their digits into an array, and compare to the array of digits for our given number.  If they match, it means our number can be rearranged to make a power of 2.
[]