Reordered Power of 2 solution and explanation
Google
9 more videos on this problem
Reordered Power of 2 | 4 APPROACHES | Leetcode 869 | codestorywithMIKcodestorywithMIK · 33:03 · 9K views
Reordered Power of 2 | Live Coding with Explanation | Leetcode - 869Algorithms Made Easy · 4:48 · 6K views
Reordered Power of 2 | leetcode 869Coding Decoded · 11:23 · 2K views
Reordered Power of 2 | LeetCode 869 | Coders CampCoders Camp · 5:49 · 742 views
Leetcode 869 Reordered Power of 2 | Google Interview Question | PythonAlgoMonster · 2:53 · 715 views
869. Reordered Power of 2 | Leetcode Daily - PythonLeetcode Daily · 5:11 · 625 views
869. Reordered Power of 2 (Leetcode Medium)Programming Live with Larry · 13:52 · 393 views
869. Reordered Power of 2 | LeetCode | MathsCoding Gist · 10:01 · 338 views
LeetCode 869. Reordered Power of 2 | PythonLea's coding · 2:37 · 209 views
Leetcode 869: Reordered Power of 2Algorithms Casts · 7:48 · 126 views
The problem
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 <= 109
Approach overview
Problem Overview: Given an integer n, determine whether you can reorder its digits so the resulting number becomes a power of two. The reordered number cannot have leading zeros. The core challenge is verifying whether any permutation of the digits matches the digits of a valid power of two.
Approach 1: Backtracking Permutations (O(d! * d) time, O(d) space)
This approach generates every permutation of the digits of n using backtracking. For each permutation, skip cases where the first digit is 0 to avoid leading zeros. Convert the permutation to a number and check whether it is a power of two using the bit trick x & (x - 1) == 0. The algorithm explores the full permutation tree, which leads to factorial complexity O(d!) where d is the number of digits. Space usage is O(d) for recursion and the permutation path. This method is straightforward and demonstrates brute‑force reasoning, but it becomes inefficient as digit count grows.
Approach 2: Digit Count Matching with Powers of Two (O(d) time, O(1) space)
The key observation: if two numbers are permutations of each other, their digit frequency counts are identical. Instead of generating permutations of n, compute a digit frequency signature for n. Then iterate through all powers of two within the integer range (from 2^0 to about 2^30 for 32-bit integers). For each power, compute its digit frequency and compare it with the signature of n. If any match occurs, a valid reordering exists. This reduces the problem to counting digits using a simple array or map from the counting pattern.
The iteration over powers of two is constant (around 31 values), so the dominant cost is building digit counts of size d. The total complexity becomes O(d) time with O(1) space since the digit array has fixed size 10. Implementations often use arrays or maps from a hash table perspective to compare signatures efficiently.
This approach avoids permutation generation entirely and converts the problem into a frequency comparison task. Conceptually it blends ideas from math and digit counting to exploit the small set of candidate numbers.
Recommended for interviews: Interviewers expect the digit-count matching approach. It shows you recognized the permutation equivalence trick and avoided factorial enumeration. Explaining the backtracking version first demonstrates baseline reasoning, but the optimized frequency comparison shows stronger algorithmic insight and leads to a clean O(d) solution.
Approach 1: Digit Count Matching with Powers of Two
One approach to solve the problem is to leverage the fact that two numbers with the same digits in different orders will have the same digit frequency (or count of each digit). For the given number n, we aim to check if its digits can be rearranged to form any power of two. To achieve this:
- Precompute all powers of two up to
10^9and store their digit frequency in a set. - For the input number
n, calculate its digit frequency and check if it exists in the set.
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
from collections import Counter
digits_count = Counter(str(n))
return any(digits_count == Counter(str(1 << i)) for i in range(31))
# Usage Example
s = Solution()
print(s.reorderedPowerOf2(1)) # Output: Trueimport java.util.Arrays;
class Solution {
public boolean reorderedPowerOf2(int n) {
char[] inputDigits = Integer.toString(n).toCharArray();
Arrays.sort(inputDigits);
for (int i = 0; i < 31; i++) {
char[] powerDigits = Integer.toString(1 << i).toCharArray();
Arrays.sort(powerDigits);
if (Arrays.equals(inputDigits, powerDigits)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reorderedPowerOf2(1)); // Output: true
}
}#include <bits/stdc++.h>
using namespace std;
bool reorderedPowerOf2(int n) {
string s = to_string(n);
sort(s.begin(), s.end());
for (int i = 0; i < 31; i++) {
string t = to_string(1 << i);
sort(t.begin(), t.end());
if (s == t) return true;
}
return false;
}
int main() {
int n = 10;
cout << boolalpha << reorderedPowerOf2(n) << endl;
return 0;
}function reorderedPowerOf2(n) {
const countDigits = (num) => Array.from(num.toString()).sort().join('');
const nDigits = countDigits(n);
for (let i = 0; i < 31; i++) {
if (nDigits === countDigits(1 << i)) {
return true;
}
}
return false;
}
console.log(reorderedPowerOf2(1)); // Output: true#include <stdbool.h>
#include <stdio.h>
#include <string.h>
bool reorderedPowerOf2(int n) {
int countDigits[10] = {0};
int num = n;
while (num > 0) {
countDigits[num % 10]++;
num /= 10;
}
for (int i = 0; i < 31; ++i) {
int powerDigits[10] = {0};
int powerOfTwo = 1 << i;
num = powerOfTwo;
while (num > 0) {
powerDigits[num % 10]++;
num /= 10;
}
bool match = true;
for (int j = 0; j < 10; ++j) {
if (countDigits[j] != powerDigits[j]) {
match = false;
break;
}
}
if (match) {
return true;
}
}
return false;
}
int main() {
int n = 1;
printf("%s\n", reorderedPowerOf2(n) ? "true" : "false");
return 0;
}using System;
using System.Linq;
public class Solution {
public bool ReorderedPowerOf2(int n) {
var inputDigits = n.ToString().OrderBy(c => c).ToArray();
for (int i = 0; i < 31; i++) {
var powerDigits = (1 << i).ToString().OrderBy(c => c).ToArray();
if (inputDigits.SequenceEqual(powerDigits)) {
return true;
}
}
return false;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.ReorderedPowerOf2(1)); // Output: True
}
}Python's solution leverages the collections.Counter to tally digit occurrences. Comparisons are made between the input number's digit counts and those of powers of two, identifying any matching permutations.
Time Complexity: O(1) due to bounded loop iterations and integer operations.
Space Complexity: O(1) since the space for counters is limited.
Approach 2: Backtracking Approach
A backtracking method can be employed by generating permutations of the digits of the number n and checking if any results in a power of two. Given the constraint, this method needs optimization to efficiently discard invalid permutations early.
- Generate all valid permutations of
n's digits where the leading digit isn't zero. - Track numbers that form powers of two during permutations.
from itertools import permutations
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
nStr = str(n)
return any(perm[0] != '0' and self.isPowerOf2(int(perm))
for perm in permutations(nStr))
def isPowerOf2(self, num: int) -> bool:
return (num & (num - 1)) == 0
# Usage Example
s = Solution()
print(s.reorderedPowerOf2(10)) # Output: Falseimport java.util.*;
class Solution {
public boolean reorderedPowerOf2(int n) {
String nStr = String.valueOf(n);
char[] nArr = nStr.toCharArray();
Arrays.sort(nArr);
return backtrack(new boolean[nArr.length], new StringBuilder(), nArr);
}
private boolean backtrack(boolean[] used, StringBuilder perm, char[] nArr) {
if (perm.length() == nArr.length) {
String permStr = perm.toString();
if (permStr.charAt(0) != '0' && isPowerOf2(Integer.parseInt(permStr))) {
return true;
}
return false;
}
for (int i = 0; i < nArr.length; i++) {
if (used[i] || (i > 0 && nArr[i] == nArr[i - 1] && !used[i - 1])) continue;
used[i] = true;
perm.append(nArr[i]);
if (backtrack(used, perm, nArr)) return true;
perm.deleteCharAt(perm.length() - 1);
used[i] = false;
}
return false;
}
private boolean isPowerOf2(int num) {
return (num & (num - 1)) == 0;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reorderedPowerOf2(10)); // Output: false
}
}#include <bits/stdc++.h>
using namespace std;
bool canFormPowerOf2(string perm) {
if (perm[0] == '0') return false;
int num = stoi(perm);
return (num & (num - 1)) == 0;
}
bool backtracking(string& nStr, string perm, vector<bool>& used) {
if (perm.size() == nStr.size()) {
return canFormPowerOf2(perm);
}
for (int i = 0; i < nStr.size(); ++i) {
if (used[i] || (i > 0 && nStr[i] == nStr[i-1] && !used[i-1])) continue;
used[i] = true;
if (backtracking(nStr, perm + nStr[i], used)) return true;
used[i] = false;
}
return false;
}
bool reorderedPowerOf2(int n) {
string nStr = to_string(n);
vector<bool> used(nStr.size(), false);
sort(nStr.begin(), nStr.end());
return backtracking(nStr, "", used);
}
int main() {
int n = 10;
cout << std::boolalpha << reorderedPowerOf2(n) << endl;
return 0;
}function reorderedPowerOf2(n) {
const isPowerOf2 = (num) => (num & (num - 1)) === 0;
const permute = (str) => {
let result = [];
if (str.length === 1) {
return [str];
}
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (i > 0 && char === str[i - 1]) continue; // Skip duplicates.
const remainingStr = str.slice(0, i) + str.slice(i + 1);
for (const perm of permute(remainingStr)) {
result.push(char + perm);
}
}
return result;
};
const nStr = n.toString();
return permute(nStr).some(perm => perm[0] !== '0' && isPowerOf2(Number(perm)));
}
console.log(reorderedPowerOf2(10)); // Output: false/* C does not have a straightforward way to implement permutations visually.
Such implementation in C typically requires additional manual handling and
recursion, which can get significantly complex and is error-prone in this format.using System;
using System.Linq;
using System.Collections.Generic;
public class Solution {
public bool ReorderedPowerOf2(int n) {
string nStr = n.ToString();
var digits = nStr.ToArray();
return Permute(digits, 0).Any(num => IsPowerOf2(num));
}
private bool IsPowerOf2(int num) {
return (num & (num - 1)) == 0;
}
public IEnumerable<int> Permute(char[] digits, int start) {
if (start == digits.Length - 1) {
yield return int.Parse(new string(digits));
}
else
{
for (int i = start; i < digits.Length; i++) {
Swap(digits, start, i);
foreach (var num in Permute(digits, start + 1)) {
if (num.ToString()[0] != '0') yield return num;
}
Swap(digits, start, i);
}
}
}
private void Swap(char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.ReorderedPowerOf2(10)); // Output: False
}
}Python uses the itertools.permutations for generating permutations of the string representation of n. It filters permutations to exclude those starting with '0' and verifies if constructed numbers are powers of two.
Time Complexity: O(n!) due to permutations.
Space Complexity: O(n) for maintaining permutations.
Approach 3: Enumeration
We can enumerate all powers of 2 in the range [1, 10^9] and check if their digit composition is the same as the given number.
Define a function f(x) that represents the digit composition of number x. We can convert the number x into an array of length 10, or a string sorted by digit size.
First, we calculate the digit composition of the given number n as target = f(n). Then, we enumerate i starting from 1, shifting i left by one bit each time (equivalent to multiplying by 2), until i exceeds 10^9. For each i, we calculate its digit composition and compare it with target. If they are the same, we return true; if the enumeration ends without finding the same digit composition, we return false.
Time complexity O(log^2 M), space complexity O(log M). Where M is the upper limit of the input range {10}^9 for this problem.
function reorderedPowerOf2(n: number): boolean {
const f = (x: number) => {
const cnt = Array(10).fill(0);
while (x > 0) {
cnt[x % 10]++;
x = (x / 10) | 0;
}
return cnt.join(',');
};
const target = f(n);
for (let i = 1; i <= 1_000_000_000; i <<= 1) {
if (target === f(i)) {
return true;
}
}
return false;
}func reorderedPowerOf2(n int) bool {
target := f(n)
for i := 1; i <= 1000000000; i <<= 1 {
if bytes.Equal(target, f(i)) {
return true
}
}
return false
}
func f(x int) []byte {
cnt := make([]byte, 10)
for x > 0 {
cnt[x%10]++
x /= 10
}
return cnt
}impl Solution {
pub fn reordered_power_of2(n: i32) -> bool {
fn f(mut x: i32) -> [u8; 10] {
let mut cnt = [0u8; 10];
while x > 0 {
cnt[(x % 10) as usize] += 1;
x /= 10;
}
cnt
}
let target = f(n);
let mut i = 1i32;
while i <= 1_000_000_000 {
if target == f(i) {
return true;
}
i <<= 1;
}
false
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Digit Count Matching with Powers of Two | Time Complexity: O(1) due to bounded loop iterations and integer operations. |
| Backtracking Approach | Time Complexity: O(n!) due to permutations. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Permutations | O(d! * d) | O(d) | Useful for demonstrating brute-force reasoning or when digit count is very small |
| Digit Count Matching with Powers of Two | O(d) | O(1) | Best general solution; avoids permutations and compares digit frequency with all valid powers of two |
Frequently asked questions
Is Reordered Power of 2 easy or hard?
The problem is rated Medium because the brute-force idea is simple but inefficient. Recognizing that permutations share the same digit frequency and reducing the search to powers of two requires a key insight.
Reordered Power of 2 Python/Java solution
In Python or Java, compute a digit count for n and compare it with counts of numbers generated by shifting powers of two (1 << k). If any count matches, return true. This approach avoids generating permutations and keeps the implementation short and efficient.
How to solve Reordered Power of 2 in O(n)?
Treat the digits as a frequency signature. Count digits of n using an array of size 10. Then generate powers of two within the integer range and compare their digit counts with the signature of n. Since only ~31 powers are checked, the runtime is effectively linear in the number of digits.
What is the best approach for Reordered Power of 2?
The most efficient approach compares digit frequencies. Count how many times each digit appears in n, then compare this signature with every power of two (2^0 to 2^30). If any power of two has the same digit count, the digits can be reordered to form that number. This runs in O(d) time where d is the number of digits.
Is Reordered Power of 2 asked at Google/Amazon/Meta?
Permutation and digit-count problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving frequency counting, anagram detection, or numeric permutations are common screening questions.
What data structure is used in Reordered Power of 2?
The core structure is a fixed-size digit frequency array of length 10. Some implementations use a hash map or a sorted string representation, but the array-based counting approach is the fastest and simplest.
What is the time complexity of Reordered Power of 2?
The optimal digit-count solution runs in O(d) time and O(1) space. You compute the digit frequency of n and compare it against about 31 powers of two. A brute-force permutation approach takes O(d! * d) time because it generates all possible digit arrangements.