Reordered Power of 2 - Practice Coding Problems

Reordered Power of 2 - Problem

You are given an integer n. We can reorder the digits of n 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: true

💡 Note: 1 is already a power of 2 (2⁰ = 1), so no reordering needed

Example 2 — Reordering Required

$ Input: n = 46

› Output: true

💡 Note: We can reorder 46 to get 64, which is 2⁶ = 64

Example 3 — No Valid Arrangement

$ Input: n = 24

› Output: false

💡 Note: No arrangement of digits 2,4 can form a power of 2 (42 and 24 are both not powers of 2)

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given number n = 46 with digits [4,6]

Process

Check if digits can form any power of 2: 1,2,4,8,16,32,64,128...

Output

Found match: 64 uses same digits as 46

Key Takeaway

🎯 Key Insight: Two numbers can be rearranged into each other if they have identical digit frequency patterns

Asked in

G Google 12 f Facebook 8 M Microsoft 6

The key insight is that two numbers can be rearranged into each other if and only if they have identical digit frequency patterns. Best approach is to count input digits and compare with pre-computed power-of-2 patterns. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Pre-computed Powers Lookup	O(log n)	O(1)	Pre-compute all valid power of 2 digit patterns and use hash map for O(1) lookup
Digit Frequency Comparison	O(log n)	O(1)	Count digit frequencies and compare with frequencies of powers of 2
Generate All Permutations	O(k! × k)	O(k!)	Generate all permutations of digits and check if any is a power of 2

Pre-computed Powers Lookup — Algorithm Steps

Pre-compute digit frequencies for all powers of 2 up to 10^9
Store frequency patterns in a set
Count digit frequencies of input
Check if input pattern exists in pre-computed set

Visualization

Tap to expand

Step-by-Step Walkthrough

Pre-compute

Store patterns: {1→[1,0,0...], 2→[0,1,0...], 4→[0,0,0,1...]...}

Count Input

46 → [0,0,0,0,1,0,1,0,0,0]

Hash Lookup

Check if pattern exists in set - O(1) operation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_POWERS 50

void countDigits(int num, int* count) {
    for (int i = 0; i < 10; i++) count[i] = 0;
    
    char str[12];
    sprintf(str, "%d", num);
    
    for (int i = 0; str[i]; i++) {
        count[str[i] - '0']++;
    }
}

bool arraysEqual(int* a, int* b) {
    for (int i = 0; i < 10; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

bool solution(int n) {
    // Pre-compute all power patterns
    static int powerPatterns[MAX_POWERS][10];
    static bool initialized = false;
    static int numPatterns = 0;
    
    if (!initialized) {
        long long power = 1;
        while (power <= 1000000000LL && numPatterns < MAX_POWERS) {
            countDigits(power, powerPatterns[numPatterns]);
            numPatterns++;
            power *= 2;
        }
        initialized = true;
    }
    
    int inputPattern[10];
    countDigits(n, inputPattern);
    
    for (int i = 0; i < numPatterns; i++) {
        if (arraysEqual(inputPattern, powerPatterns[i])) {
            return true;
        }
    }
    
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Only need to count digits of input number, lookup is O(1)

⚡ Linearithmic

Space Complexity

O(1)

Pre-computed set has fixed size (~30 entries)

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Pre-computed Powers Lookup — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler