leetcode

commit ee529c9e77c3d65b74086a2afb111b1fcf030ff2
parent b1b4bfa3a2c70bf364080ccf0e0014cd6ae80054
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 17 Dec 2025 10:08:25 -0700

1238. circular permutation in binary representation

Diffstat:
A
circular_permutation_binary_rep.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
circular_permutation_binary_rep.py
 | 
24
++++++++++++++++++++++++

2 files changed, 68 insertions(+), 0 deletions(-)
diff --git a/circular_permutation_binary_rep.c b/circular_permutation_binary_rep.c
@@ -0,0 +1,44 @@
+// 1238. Circular Permutation in Binary Representation
+#include "leetcode.h"
+
+/*
+ * given 2 integers 'n' and 'start', your task is to return any permutation of
+ * '(0, 1, 2, ..., 2^n - 1)' such that 'p[0] = start', 'p[i]' and 'p[i + 1]'
+ * differ by only one bit in their binary representation, and 'p[0]' and '[p2^n
+ * - 1]' must also differ by oly one bit in their binary repesentation.
+ */
+
+int *circularPermutation(int n, int start, int *returnSize) {
+  int x = pow(2, n), curr = 1, begin;
+  *returnSize = x;
+  int *tmp = (int *)malloc(x * sizeof(int));
+  tmp[0] = 0;
+  for (int i = 0; i < n; i++) {
+    for (int j = 0; j < curr; j++)
+      tmp[curr + j] = tmp[curr - 1 - j] + (1 << i);
+    curr *= 2;
+  }
+  for (int i = 0; i < x; i++)
+    if (tmp[i] == start) {
+      begin = i;
+      break;
+    }
+  int *ans = (int *)malloc(x * sizeof(int));
+  memcpy(ans, &tmp[begin], (x - begin) * sizeof(int));
+  memcpy(&ans[x - begin], tmp, begin * sizeof(int));
+  free(tmp);
+  return ans;
+}
+
+int main() {
+  int rs1, *cp1 = circularPermutation(2, 3, &rs1);
+  int rs2, *cp2 = circularPermutation(3, 2, &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", cp1[i]); // expect: 3 2 0 1
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", cp2[i]); // expect: 2 6 7 5 4 0 1 3
+  printf("\n");
+  free(cp1);
+  free(cp2);
+}
diff --git a/circular_permutation_binary_rep.py b/circular_permutation_binary_rep.py
@@ -0,0 +1,24 @@
+# 1238. Circular Permutation in Binary Representation
+
+"""
+given 2 integers 'n' and 'start', your task is to return any permutation of
+'(0, 1, 2, ..., 2^n - 1)' such that 'p[0] = start', 'p[i]' and 'p[i + 1]'
+differ by only one bit in their binary representation, and 'p[0]' and '[p2^n
+- 1]' must also differ by oly one bit in their binary repesentation.
+"""
+
+
+class Solution(object):
+    def circularPermutation(self, n, start):
+        """
+        :type n: int
+        :type start: int
+        :rtype: List[int]
+        """
+        return [start ^ i ^ i >> 1 for i in range(1 << n)]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.circularPermutation(n=2, start=3))
+    print(obj.circularPermutation(n=3, start=2))