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

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 digits, and thus permutations and each requires conversion to integer and checking power of two (assuming O(1) constant). Thus overall time complexity is

The space complexity is 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 .

–EOF (The Ultimate Computing & Technology Blog) —