Jobs

Interviews

Discussions

Reordered Power of 2

Medium

Asked by:

5 views

Topics:

ArraysStringsBit Manipulation

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⁹

Try coding it in LeetCode

Reordered Power of 2

Medium

Asked by:

5 views

Topics:

ArraysStringsBit Manipulation

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⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the input integer N?
Can the input integer N be zero or negative?
By 'reordered', do you mean any permutation of the digits, or are there any restrictions on the order?
If there is no reordering of the digits that forms a power of 2, what should I return (e.g., false, null, an exception)?
Should I consider leading zeros in the reordered number as invalid?

Brute Force Solution

Approach

The core idea is to check every single possible arrangement of the digits. We generate each possible arrangement, and then we check if that arrangement forms a power of 2.

Here's how the algorithm would work step-by-step:

Take the number given, and consider all possible rearrangements of its digits.
For each rearrangement, construct the number that those digits represent.
Check if the constructed number is a power of 2. Powers of 2 are numbers like 1, 2, 4, 8, 16, and so on.
If you find a rearrangement that creates a power of 2, then the answer is yes, and you can stop looking.
If you've checked every single rearrangement and none of them are a power of 2, then the answer is no.

Code Implementation

def reordered_power_of_2(number):

    from itertools import permutations

    number_string = str(number)
    # Generate all possible permutations of the digits.
    for permutation_tuple in permutations(number_string):
        rearranged_number_string = "".join(permutation_tuple)

        # Skip leading zeros to avoid invalid numbers.
        if rearranged_number_string[0] == '0' and len(rearranged_number_string) > 1:
            continue

        rearranged_number = int(rearranged_number_string)

        # Check if the rearranged number is a power of 2.
        if rearranged_number > 0 and (rearranged_number & (rearranged_number - 1)) == 0:
            return True

    # If no power of 2 is found after checking all permutations.
    return False

Big(O) Analysis

Time Complexity

O(n! * log n) – Let n be the number of digits in the input number. The algorithm first generates all permutations of the digits, which takes O(n!) time since there are n! possible arrangements. For each permutation, we construct the number and check if it's a power of 2. Checking if a number is a power of 2 involves taking the logarithm of that number which has a complexity of O(log n) where n here refers to the magnitude of the generated number, not the number of digits. Therefore, the overall time complexity is O(n! * log n).

Space Complexity

O(N) – The dominant space complexity comes from generating all possible rearrangements of the digits. While the plain English explanation doesn't explicitly mention a data structure for storing these rearrangements, generating permutations typically involves storing the digits in an array or list with a size related to the number of digits in the input number N (where N is the number of digits in the input number). This storage is used for constructing and manipulating the permutations before checking if they are a power of 2. Thus, the auxiliary space required scales linearly with the number of digits in the input number. Recursion might be used under the hood for computing permutations, taking up N space on the stack as well.

Optimal Solution

Approach

The problem asks if we can rearrange a number to form a power of 2. The most efficient way to solve this is to avoid generating all rearrangements. Instead, we focus on the properties of power of 2s and use counting to determine if a rearrangement is possible.

Here's how the algorithm would work step-by-step:

First, figure out how many times each digit appears in the given number.
Then, consider all the powers of 2 that have the same number of digits as the input number.
For each power of 2, determine how many times each digit appears in that power of 2.
Finally, check if the digit counts for the input number match the digit counts for any of the powers of 2 that you are considering. If they match, it means you can rearrange the digits of the input number to form that power of 2.

Code Implementation

def reordered_power_of_2(number):
    number_string = str(number)

    # Count the occurrences of each digit in the given number
    number_digit_counts = {}
    for digit in number_string:
        number_digit_counts[digit] = number_digit_counts.get(digit, 0) + 1

    # Iterate through powers of 2 within a reasonable range
    for i in range(60):
        power_of_2 = 1 << i
        power_of_2_string = str(power_of_2)

        # Only consider powers of 2 with the same number of digits
        if len(power_of_2_string) != len(number_string):
            continue

        power_of_2_digit_counts = {}
        for digit in power_of_2_string:
            power_of_2_digit_counts[digit] = power_of_2_digit_counts.get(digit, 0) + 1

        # Check if the digit counts match
        if number_digit_counts == power_of_2_digit_counts:
            return True

    # If no power of 2 matches the digit counts, return False.
    return False

Big(O) Analysis

Time Complexity

O(log n) – Let n be the input number. We first count the frequency of each digit in n, which takes O(log n) time where log n is the number of digits in n. Then, we iterate through powers of 2, but only up to the number with the same number of digits as n, which is at most a logarithmic number of iterations since powers of 2 increase exponentially. For each power of 2, we also count digit frequencies in O(log n) time. Since the outer loop runs at most O(log n) times and the inner operation is O(log n), the dominant factor becomes O(log n).

Space Complexity

O(1) – The auxiliary space is dominated by the digit count arrays. The plain English explanation details counting the frequency of digits in the input number and in powers of 2. Since we are dealing with digits (0-9), the size of these count arrays is fixed at 10, irrespective of the input number's size, N (where N is the number of digits in the input number). The number of powers of two to consider is also limited because we only consider powers of two with the same number of digits as the input, and integer size limitations mean there's a maximum number of powers of 2 that can be represented. Therefore, the space used remains constant.

Edge Cases

Case	How to Handle
Input is 0	Handle 0 as a special case as it doesn't fit the digit-permutation logic of powers of 2; could return true if power of 2 is 1
Input is a negative number	Return false immediately since powers of 2 are always positive.
Input has leading zeros	The permutation logic should inherently handle leading zeros since it considers all digit arrangements.
Input is a large number causing integer overflow in intermediate calculations	Use long data type in Java/C++ to avoid overflow during digit counts and comparisons with powers of 2.
No power of 2 is a permutation of the input digits	Return false after checking all relevant powers of 2 (up to the length of the integer input).
Input with repeated digits such as 11111...	The digit-counting approach should handle repeated digits correctly without special modification.
Integer with digits sorted in descending order	Ensure the permutation algorithm correctly generates all possible combinations, including the largest magnitude number.
The smallest possible valid input of '1'	Return true as 1 is a power of 2.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the input integer N?
Can the input integer N be zero or negative?
By 'reordered', do you mean any permutation of the digits, or are there any restrictions on the order?
If there is no reordering of the digits that forms a power of 2, what should I return (e.g., false, null, an exception)?
Should I consider leading zeros in the reordered number as invalid?

Brute Force Solution

Approach

The core idea is to check every single possible arrangement of the digits. We generate each possible arrangement, and then we check if that arrangement forms a power of 2.

Here's how the algorithm would work step-by-step:

Take the number given, and consider all possible rearrangements of its digits.
For each rearrangement, construct the number that those digits represent.
Check if the constructed number is a power of 2. Powers of 2 are numbers like 1, 2, 4, 8, 16, and so on.
If you find a rearrangement that creates a power of 2, then the answer is yes, and you can stop looking.
If you've checked every single rearrangement and none of them are a power of 2, then the answer is no.

Code Implementation

def reordered_power_of_2(number):

    from itertools import permutations

    number_string = str(number)
    # Generate all possible permutations of the digits.
    for permutation_tuple in permutations(number_string):
        rearranged_number_string = "".join(permutation_tuple)

        # Skip leading zeros to avoid invalid numbers.
        if rearranged_number_string[0] == '0' and len(rearranged_number_string) > 1:
            continue

        rearranged_number = int(rearranged_number_string)

        # Check if the rearranged number is a power of 2.
        if rearranged_number > 0 and (rearranged_number & (rearranged_number - 1)) == 0:
            return True

    # If no power of 2 is found after checking all permutations.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out how many times each digit appears in the given number.
Then, consider all the powers of 2 that have the same number of digits as the input number.
For each power of 2, determine how many times each digit appears in that power of 2.
Finally, check if the digit counts for the input number match the digit counts for any of the powers of 2 that you are considering. If they match, it means you can rearrange the digits of the input number to form that power of 2.

Code Implementation

def reordered_power_of_2(number):
    number_string = str(number)

    # Count the occurrences of each digit in the given number
    number_digit_counts = {}
    for digit in number_string:
        number_digit_counts[digit] = number_digit_counts.get(digit, 0) + 1

    # Iterate through powers of 2 within a reasonable range
    for i in range(60):
        power_of_2 = 1 << i
        power_of_2_string = str(power_of_2)

        # Only consider powers of 2 with the same number of digits
        if len(power_of_2_string) != len(number_string):
            continue

        power_of_2_digit_counts = {}
        for digit in power_of_2_string:
            power_of_2_digit_counts[digit] = power_of_2_digit_counts.get(digit, 0) + 1

        # Check if the digit counts match
        if number_digit_counts == power_of_2_digit_counts:
            return True

    # If no power of 2 matches the digit counts, return False.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	Handle 0 as a special case as it doesn't fit the digit-permutation logic of powers of 2; could return true if power of 2 is 1
Input is a negative number	Return false immediately since powers of 2 are always positive.
Input has leading zeros	The permutation logic should inherently handle leading zeros since it considers all digit arrangements.
Input is a large number causing integer overflow in intermediate calculations	Use long data type in Java/C++ to avoid overflow during digit counts and comparisons with powers of 2.
No power of 2 is a permutation of the input digits	Return false after checking all relevant powers of 2 (up to the length of the integer input).
Input with repeated digits such as 11111...	The digit-counting approach should handle repeated digits correctly without special modification.
Integer with digits sorted in descending order	Ensure the permutation algorithm correctly generates all possible combinations, including the largest magnitude number.
The smallest possible valid input of '1'	Return true as 1 is a power of 2.