README.md

869. 重新排序得到 2 的幂

English Version

题目描述

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

 

示例 1：

输入：1
输出：true

示例 2：

输入：10
输出：false

示例 3：

输入：16
输出：true

示例 4：

输入：24
输出：false

示例 5：

输入：46
输出：true

 

提示：

1. 1 <= N <= 10^9

解法

Python3

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def convert(n):
            counter = [0] * 10
            while n > 0:
                counter[n % 10] += 1
                n //= 10
            return counter

        i, s = 1, convert(n)
        while i <= 10 ** 9:
            if convert(i) == s:
                return True
            i <<= 1
        return False

Java

class Solution {
    public boolean reorderedPowerOf2(int n) {
        String s = convert(n);
        for (int i = 1; i <= Math.pow(10, 9); i <<= 1) {
            if (s.equals(convert(i))) {
                return true;
            }
        }
        return false;
    }

    private String convert(int n) {
        char[] counter = new char[10];
        while (n > 0) {
            ++counter[n % 10];
            n /= 10;
        }
        return new String(counter);
    }
}

C++

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        vector<int> s = convert(n);
        for (int i = 1; i <= pow(10, 9); i <<= 1)
            if (s == convert(i)) return true;
        return false;
    }

    vector<int> convert(int n) {
        vector<int> counter(10);
        while (n)
        {
            ++counter[n % 10];
            n /= 10;
        }
        return counter;
    }
};

Go

func reorderedPowerOf2(n int) bool {
	convert := func(n int) []byte {
		counter := make([]byte, 10)
		for n > 0 {
			counter[n%10]++
			n /= 10
		}
		return counter
	}

	s := convert(n)
	for i := 1; i <= 1e9; i <<= 1 {
		if bytes.Equal(s, convert(i)) {
			return true
		}
	}
	return false
}

...