algoadvance

Leetcode 869. Reordered Power of 2

Problem Statement

We need to determine if the digits of an integer ( N ) can be reordered to form a power of 2. In other words, the goal is to check if there exists some permutation of the digits of ( N ) that is a power of 2.

Clarifying Questions

  1. Range of N: What is the range of the integer ( N )?
    • Response: The problem constraints usually follow ( 1 \leq N \leq 10^9 ).
  2. Leading zeroes: Are we allowed to have leading zeroes in the permutations?
    • Response: No, leading zeroes are not valid as they do not form valid integers.
  3. Negative numbers: Can ( N ) be negative?
    • Response: Generally, ( N ) is assumed to be positive in such problems.

Strategy

  1. Counting Digits: The order of the digits doesn’t matter, just their count. We can make use of the fact that for a number to be a permutation of another, their digit counts must match.

  2. Generate Power of 2s: Compute all possible powers of 2 that are within the range ( 1 \leq x \leq 10^9 ). We only need 30 such numbers since ( 2^{30} ) is slightly over ( 10^9 ).

  3. Comparison by Digit Counting:

    • Convert ( N ) to a string and sort its digits.
    • Do the same for all powers of 2 within the range.
    • Check if any of these representations match.

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// Function to count digits in a number and return it as a sorted string
std::string countDigits(int n) {
    std::string s = std::to_string(n);
    std::sort(s.begin(), s.end());
    return s;
}

bool reorderedPowerOf2(int N) {
    std::string N_digits = countDigits(N);
    for (int i = 0; i < 31; ++i) {
        int powerOf2 = 1 << i; // 2^i
        if (N_digits == countDigits(powerOf2)) {
            return true;
        }
    }
    return false;
}

int main() {
    int N = 821; // Example usage
    if (reorderedPowerOf2(N)) {
        std::cout << N << " can be reordered to form a power of 2.\n";
    } else {
        std::cout << N << " cannot be reordered to form a power of 2.\n";
    }
    return 0;
}

Time Complexity

Combining these, the overall time complexity is ( O(30 \times (d \log d)) \approx O(d \log d) ) considering that ( d ), the number of digits, is at most 10 for ( N \leq 10^9 ).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI