leetcode

commit 20f07f1feae9cf99ff005d379919fd9bad012f82
parent a09548594e7f57c4d6d31964f7c1d99bf2f822b2
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 10 Aug 2025 11:33:56 +0200

869. reordered power of 2

Diffstat:
A
reordered_power_2.c
 | 
30
++++++++++++++++++++++++++++++
A
reordered_power_2.py
 | 
27
+++++++++++++++++++++++++++

2 files changed, 57 insertions(+), 0 deletions(-)
diff --git a/reordered_power_2.c b/reordered_power_2.c
@@ -0,0 +1,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
+}
diff --git a/reordered_power_2.py b/reordered_power_2.py
@@ -0,0 +1,27 @@
+# 869. Reordered Power of 2
+from collections import Counter
+
+"""
+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.
+"""
+
+
+class Solution(object):
+    def reorderedPowerOf2(self, n):
+        """
+        :type n: int
+        :rtype: bool
+        """
+        cnt = Counter(str(n))
+        for i in range(31):
+            if Counter(str(1 << i)) == cnt:
+                return True
+        return False
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.reorderedPowerOf2(1))
+    print(obj.reorderedPowerOf2(10))