Question

869. 重新排序得到 2 的幂

English Version

题目描述

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

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

 

示例 1：

输入：n = 1
输出：true

示例 2：

输入：n = 10
输出：false

 

提示：

• 1 <= n <= 109

解法

方法一

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

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

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[] cnt = new char[10];
    for (; n > 0; n /= 10) {
      cnt[n % 10]++;
    }
    return new String(cnt);
  }
}

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> cnt(10);
    for (; n; n /= 10) ++cnt[n % 10];
    return cnt;
  }
};

func reorderedPowerOf2(n int) bool {
  convert := func(n int) []byte {
    cnt := make([]byte, 10)
    for ; n > 0; n /= 10 {
      cnt[n%10]++
    }
    return cnt
  }
  s := convert(n)
  for i := 1; i <= 1e9; i <<= 1 {
    if bytes.Equal(s, convert(i)) {
      return true
    }
  }
  return false
}