Teaching Kids Programming – Reordered Power of Two (Rearranging the Digits, Permutation + Counting)

Teaching Kids Programming – Reordered Power of Two (Rearranging the Digits, Permutation + Counting) | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an 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 so that the resulting number is a power of two.

Example 1:
Input: n = 1
Output: true

Example 2:
Input: n = 10
Output: false

Constraints:
1 <= n <= 10^9

Bruteforce Algorithm (Full Permutation of Digits) and Check Power of Two

The straightforward solution is to bruteforce the digits (full permutation) and then check if the reordered number is a power of two (and does not contain a leading zero).

 1 2 3 4 5 6 7 8 class Solution(object):     def reorderedPowerOf2(self, N):             for c in itertools.permutations(str(N)):             x = "".join(c)             y = int(x)             if c[0] != '0' and y & (y - 1) == 0:                 return True         return False
class Solution(object):
def reorderedPowerOf2(self, N):
for c in itertools.permutations(str(N)):
x = "".join(c)
y = int(x)
if c[0] != '0' and y & (y - 1) == 0:
return True
return False

We can use the permutations from the itertools or we can implement a Recursive Permutation like this (yield an permutation iterator):

 1 2 3 4 5 6 7 def perm(left, ans):     if left == len(nums):         yield ans     for i in range(left, len(nums)):         nums[i], nums[left] = nums[left], nums[i]         yield from perm(left + 1, ans)         nums[i], nums[left] = nums[left], nums[i]
def perm(left, ans):
if left == len(nums):
yield ans
for i in range(left, len(nums)):
nums[i], nums[left] = nums[left], nums[i]
yield from perm(left + 1, ans)
nums[i], nums[left] = nums[left], nums[i]

We can check an integer power of two by checking its binary representation e.g. any power of two has the form of 1000… in its binary format:

 1 2 def checkPowerOfTwo(x):     return x > 0 and x & (x - 1) == 0
def checkPowerOfTwo(x):
return x > 0 and x & (x - 1) == 0

Also, we can use the bin function to convert the integer to binary and then count the ‘1’ which should be only once for power of twos:

 1 2 def checkPowerOfTwo(x):     return bin(x).count('1') == 1
def checkPowerOfTwo(x):
return bin(x).count('1') == 1

We can also compute the log2 function and then make sure it is a whole integer via is_integer method:

 1 2 def checkPowerOfTwo(x):     return log2(x).is_integer()
def checkPowerOfTwo(x):
return log2(x).is_integer()

A less efficient method would be to check the value using the reverse power function (we need to truncate the integer part of the log2 value):

 1 2 3 def checkPowerOfTwo(x):     y = int(log2(x))     return 2 ** y == x
def checkPowerOfTwo(x):
y = int(log2(x))
return 2 ** y == x

Integer N has $tex_534b324ca8d5ee713e961c59de17f05f Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$ digits, and thus $tex_734c365e10cf571427ccdf7756690209 Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$ permutations and each requires $tex_a03861edf8a4a6af467f06c64d12aa7f Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$ conversion to integer and checking power of two (assuming O(1) constant). Thus overall time complexity is $tex_dac1a913a62c64ba48106c6cb363988e Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$

The space complexity is $tex_a03861edf8a4a6af467f06c64d12aa7f Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$ for storing each permutation of digits.

We could use the any method to beautify the implementation:

 1 2 3 4 class Solution(object):     def reorderedPowerOf2(self, N):             return any(c[0] != '0' and bin(int("".join(c))).count('1') == 1                    for c in itertools.permutations(str(N)))
class Solution(object):
def reorderedPowerOf2(self, N):
return any(c[0] != '0' and bin(int("".join(c))).count('1') == 1
for c in itertools.permutations(str(N)))

Check Reordered Power of Two By Counting

Since the given integer is within range of 32 bit, we certainly know the power of twos within this range, and thus we can count the digits and see if is a match.

 1 2 3 4 5 class Solution(object):     def reorderedPowerOf2(self, N):             count = Counter(str(N))         return any(count == collections.Counter(str(1 << b))                    for b in range(31))
class Solution(object):
def reorderedPowerOf2(self, N):
count = Counter(str(N))
return any(count == collections.Counter(str(1 << b))
for b in range(31))

The time/space complexity is $tex_706415edf1f886ff8f7d6adbc9eb5655 Teaching Kids Programming - Reordered Power of Two (Rearranging the Digits, Permutation + Counting) algorithms math Permutation python teaching kids programming youtube video$.

GD Star Rating