LeetCode Solution: 869. Reordered Power of 2

#leetcode #dsa #programming #tutorial

Unraveling LeetCode 869: Can Your Number Shuffle into a Power of Two?

Hey everyone! Vansh2710 here, ready to tackle another intriguing LeetCode challenge. Today, we're diving into problem 869, "Reordered Power of 2." This problem sounds like a fun riddle: given a number, can you rearrange its digits to form a power of two? Let's break it down!

📝 Problem Explanation

You're given an integer n. Your task is to figure out if you can reorder its digits in any way to form a new number that is a power of two.

Important Rules:

Reordering: You can arrange the digits of n in any order.
Leading Digit: The new number you form cannot have a leading zero (unless the number itself is just '0', which isn't a power of two we're interested in here).
Power of Two: The resulting number must be a power of two (i.e., 1, 2, 4, 8, 16, 32, ... which are 2^0, 2^1, 2^2, and so on).

Let's look at some examples:

Example 1: n = 1
- The digits of n are just 1.
- Can we reorder 1? Well, it's already 1.
- Is 1 a power of two? Yes, 2^0 = 1.
- Output: true
Example 2: n = 10
- The digits of n are 1 and 0.
- Possible reorderings: 10 (leading digit not zero), 01 (leading digit is zero, so invalid).
- Is 10 a power of two? No.
- Output: false

The constraints tell us 1 <= n <= 10^9. This is a crucial piece of information!

🤔 Intuition: The "Aha!" Moment

When you see a problem asking if you can "reorder digits" to form something specific, a common technique springs to mind: digit frequency counting!

Think about it: if two numbers are just reorderings of each other, they must have the exact same count of each digit. For example, 123 and 312 both have one 1, one 2, and one 3.

So, our problem boils down to:

Take the input number n.
Count how many times each digit (0-9) appears in n.
Now, how do we check if any power of two can be formed from these digits? Instead of trying to generate permutations of n (which can be a lot!), what if we just check a list of known powers of two?

This is where the constraint n <= 10^9 becomes our best friend.

n can have at most 10 digits (e.g., 1,000,000,000).
Powers of two quickly grow!
- 2^0 = 1
- 2^1 = 2
- ...
- 2^9 = 512 (3 digits)
- 2^10 = 1024 (4 digits)
- ...
- 2^29 = 536,870,912 (9 digits)
- 2^30 = 1,073,741,824 (10 digits)
- 2^31 would exceed the int limit and also have too many digits if n maxes out at 10.

So, we only need to check a relatively small list of powers of two (from 2^0 up to 2^30 or so). For each power of two in this list, we can count its digit frequencies and compare them to the digit frequencies of our input n. If we find a match, we've solved it!

🪜 Approach: Step-by-Step Logic

Here's the detailed plan based on our intuition:

Count Digits for n:
- Create an array (or vector) of size 10, initialized to zeros. Each index i will store the count of digit i.
- Convert n to a string.
- Iterate through each character (digit) in the string, convert it back to an integer, and increment its count in our array.
Iterate Powers of Two:
- Start a loop from i = 0 up to 30 (or 31 if you want to be super safe, covering 2^0 to 2^30).
- In each iteration, calculate current_power_of_2 = 1 << i (which is a fast way to get 2^i).
Count Digits for current_power_of_2:
- For each current_power_of_2, perform the same digit counting process as we did for n. Store these counts in a temporary array.
Compare Digit Counts:
- Compare the digit count array of n (from Step 1) with the digit count array of current_power_of_2 (from Step 3).
- If both arrays are identical (meaning they have the same counts for all digits 0-9), then we've found a power of two that can be formed by reordering n's digits. In this case, immediately return true.
No Match Found:
- If the loop finishes without finding any matching power of two, it means no such rearrangement exists. Return false.

Why this works: The leading digit constraint ("leading digit is not zero") is automatically handled because powers of two (other than 2^0=1) are always positive and never start with zero. Our digit counting only cares about the set of digits, not their order initially. If the digit counts match, it means we can form that power of two, and since it's a valid power of two, its leading digit will never be zero (unless it's a single-digit '0', which isn't a power of two, or if n itself were 0, but n >= 1).

💻 Code

Here's the C++ implementation of our approach:

class Solution {
public:
    // Helper function to count digit frequencies for a given number
    // It returns a vector of size 10, where index i stores the count of digit i.
    std::vector<int> getDigitCounts(int num) {
        std::vector<int> counts(10, 0); // Initialize counts for digits 0-9 to zero
        std::string s = std::to_string(num); // Convert the number to a string

        // Iterate through each character (digit) in the string
        for (char c : s) {
            counts[c - '0']++; // Increment the count for the corresponding digit
        }
        return counts; // Return the frequency map
    }

    bool reorderedPowerOf2(int n) {
        // Step 1: Get digit frequency counts for the input number 'n'
        std::vector<int> n_digit_counts = getDigitCounts(n);

        // Step 2: Iterate through all relevant powers of 2
        // We check powers from 2^0 up to 2^30.
        // 2^0 = 1
        // ...
        // 2^29 = 536,870,912 (9 digits)
        // 2^30 = 1,073,741,824 (10 digits)
        // Since n <= 10^9, n can have at most 10 digits.
        // Any power of two with more than 10 digits, or fewer digits but different counts,
        // will automatically not match. So checking up to 2^30 is sufficient.
        for (int i = 0; i < 31; ++i) { // Loop from i=0 to i=30 (inclusive)
            int powerOf2 = 1 << i; // Calculate 2 raised to the power of i

            // Step 3: Get digit frequency counts for the current power of 2
            std::vector<int> current_power_digit_counts = getDigitCounts(powerOf2);

            // Step 4: Compare the digit frequency counts
            // If the counts are identical, it means we can reorder the digits of 'n'
            // to form this 'powerOf2'.
            if (n_digit_counts == current_power_digit_counts) {
                return true; // Found a match, so return true
            }
        }

        // If the loop completes without finding any matching power of two,
        // then it's not possible to reorder 'n' into a power of two.
        return false;
    }
};

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity:
- n can be up to 10^9, which means it has at most 10 digits (i.e., log10(n) digits). Let D be the maximum number of digits (here, D = 10).
- The getDigitCounts function:
  - to_string(num) takes O(D) time.
  - The loop iterates D times.
  - So, getDigitCounts is O(D).
- The main reorderedPowerOf2 function:
  - Calls getDigitCounts(n) once: O(D).
  - The loop runs 31 times (for i from 0 to 30). Let P be the number of powers of two we check (here, P = 31).
  - Inside the loop, getDigitCounts(powerOf2) is called: O(D) (since powers of two up to 2^30 also have at most D=10 digits).
  - Comparing std::vector<int> takes O(10) which is O(D) as it compares each of the 10 elements.
- Total Time Complexity: O(D) + P * (O(D) + O(D)) = O(D * P).
- Given D = 10 and P = 31, this is roughly 10 * 31 = 310 operations. This is extremely efficient! It's practically constant time.
Space Complexity:
- The getDigitCounts function uses a std::vector<int> of size 10 to store digit counts. This size is fixed, regardless of n.
- The reorderedPowerOf2 function also uses two std::vector<int> of size 10.
- Total Space Complexity: O(1) (constant space), as the storage required does not grow with the input n.

🔑 Key Takeaways

Digit Frequency for Permutations: When a problem involves checking if numbers can be formed by "reordering" or "permuting" digits, counting digit frequencies is a powerful and often more efficient alternative than generating actual permutations.
Leverage Constraints: The n <= 10^9 constraint was crucial. It limited our search space for powers of two to a very small, manageable number, turning what could be a complex permutation problem into a simple fixed-loop iteration.
Powers of Two: Understanding how fast powers of two grow helps in setting appropriate loop bounds.
Helper Functions: Breaking down repetitive logic (like digit counting) into a helper function makes your code cleaner, more readable, and easier to debug.

This problem is a fantastic example of how understanding constraints and choosing the right data structure/technique can simplify a seemingly complex challenge! Keep practicing, and happy coding!

Submission Details:
Author Account: Vansh2710
Time Published: 2026-04-04 00:24:08