Solution: Reordered Power of 2

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #869 (Medium): Reordered Power of 2

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Starting with a positive 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 in a way such that the resulting number is a power of 2.

---

Examples:

Example 1:
Input:	1
Output:	true

Example 2:
Input:	10
Output:	false

Example 3:
Input:	16
Output:	true

Example 4:
Input:	24
Output:	false

Example 5:
Input:	46
Output:	true

---

Constraints:

• 1 <= N <= 10^9

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The easiest way to check if two things are shuffled versions of each other, which is what this problem is asking us to do, is to sort them both and the compare the result.

In that sense, the easiest solution here is to do exactly that: we can convert N to an array of its digits, sort it, then compare that result to the result of the same process on each power of 2.

Since the constraint upon N is 10e9, we only need to check powers in the range [0,29].

To make things easier to compare, we can always join() the resulting digit arrays into strings before comparison.

There are ways to very slightly improve the run time and memory here, but with an operation this small, it's honestly not very necessary.

---

Implementation:

Python can directly compare the lists and Java can directly compare the char arrays without needing to join them into strings. C++ can sort the strings in-place without needing to convert to an array.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var reorderedPowerOf2 = function(N) {
    let res = N.toString().split("").sort().join("")
    for (let i = 0; i < 30; i++)
        if ((1 << i).toString().split("").sort().join("") === res) return true
    return false
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def reorderedPowerOf2(self, N: int) -> bool:
        res = sorted([int(x) for x in str(N)])
        for i in range(30):
            if sorted([int(x) for x in str(1 << i)]) == res: return True
        return False

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public boolean reorderedPowerOf2(int N) {
        char[] res1 = String.valueOf(N).toCharArray();
        Arrays.sort(res1);
        for (int i = 0; i < 30; i++) {
            char[] res2 = String.valueOf(1 << i).toCharArray();
            Arrays.sort(res2);
            if (Arrays.equals(res1, res2)) return true;
        }
        return false;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    bool reorderedPowerOf2(int N) {
        string res1 = to_string(N);
        sort(res1.begin(), res1.end());
        for (int i = 0; i < 30; i++) {
            string res2 = to_string(1 << i);
            sort(res2.begin(), res2.end());
            if (res1 == res2) return true;
        }
        return false;
    }
};

Comments

[Gunalan D]

from collections import Counter
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:

        c = Counter(str(n))


        for i in range(32):
            mask = 1 << i
            val = Counter(str(mask))
            if c == val:
                return True

        return False

_similar idea _