leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

reordered_power_2.c (732B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 869. Reordered Power of 2
#include "leetcode.h"

/*
 * 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
 * an only if we can do this so that the resulting number is a power of two.
 */

static uint64_t signature(uint32_t n) {
  uint64_t res = 0;
  while (n) {
    res += 1UL << ((n % 10) * 4);
    n /= 10;
  }
  return res;
}

bool reorderedPowerOf2(int n) {
  const uint64_t sig = signature(n);
  for (int i = 0; i < 32; ++i)
    if (sig == signature(1 << i))
      return true;
  return false;
}

int main() {
  printf("%d\n", reorderedPowerOf2(1));  // expect: 1
  printf("%d\n", reorderedPowerOf2(10)); // expect: 0
}