leetcode

commit 9c151bc51e2f3a1ee54400c9930ee045122011e2
parent 3002d395e054d76524902e489fd38b32f9e0a704
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 24 Feb 2026 20:58:17 -0700

1356. sort integers by the number of 1 bits

Diffstat:
M
sort_int_1bits.c
 | 
60
+++++++++++++++++++++++-------------------------------------
M
sort_int_1bits.py
 | 
27
+++++++++++----------------

2 files changed, 34 insertions(+), 53 deletions(-)
diff --git a/sort_int_1bits.c b/sort_int_1bits.c
@@ -8,50 +8,36 @@
  * ascending order. return the array after sorting it.
  */
 
-struct pair {
-  int val;
-  int cnt;
-};
-
 int cmp(const void *a, const void *b) {
-  const struct pair pa = *(const struct pair *)a;
-  const struct pair pb = *(const struct pair *)b;
-  return pa.cnt == pb.cnt ? pa.val - pb.val : pa.cnt - pb.cnt;
-}
-
-int find(int a) {
-  int res = 0;
-  while (a) {
-    res += a % 2;
-    a /= 2;
-  }
-  return res;
+  int aa = *(int *)a, bb = *(int *)b;
+  int bca = __builtin_popcount(aa);
+  int bcb = __builtin_popcount(bb);
+  if (bca == bcb)
+    return aa < bb ? -1 : aa > bb ? 1 : 0;
+  return bca < bcb ? -1 : 1;
 }
 
-int *sortByBits(int *arr, int arr_size, int *return_size) {
-  *return_size = arr_size;
-  struct pair *p = (struct pair *)malloc(sizeof(struct pair) * arr_size);
-  for (int i = 0; i < arr_size; i++) {
-    p[i].val = arr[i];
-    p[i].cnt = find(arr[i]);
-  }
-  qsort(p, arr_size, sizeof(struct pair), cmp);
-  for (int i = 0; i < arr_size; i++)
-    arr[i] = p[i].val;
-  free(p);
+int *sortByBits(int *arr, int arrSize, int *returnSize) {
+  qsort(arr, arrSize, sizeof(int), cmp);
+  *returnSize = arrSize;
   return arr;
 }
 
 int main() {
-  int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8},
-      a2[] = {1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
-  int rs1[] = {}, rs2[] = {};
-  int *sbb1 = sortByBits(a1, ARRAY_SIZE(a1), rs1);
-  int *sbb2 = sortByBits(a2, ARRAY_SIZE(a2), rs2);
-  for (int i = 0; i < 8; i++)
-    printf("%d ", sbb1[i]); // expect: 0,1,2,4,8,3,5,6,7
+  int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}, rs1;
+  int r1[] = {0, 1, 2, 4, 8, 3, 5, 6, 7};
+  int a2[] = {1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}, rs2;
+  int r2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
+  int *sbb1 = sortByBits(a1, ARRAY_SIZE(a1), &rs1);
+  int *sbb2 = sortByBits(a2, ARRAY_SIZE(a2), &rs2);
+  for (int i = 0; i < rs1; i++) {
+    printf("%d ", sbb1[i]); // expect: 0 1 2 4 8 3 5 6 7
+    assert(sbb1[i] == r1[i]);
+  }
   printf("\n");
-  for (int i = 0; i < 11; i++)
-    printf("%d ", sbb2[i]); // expect: 1,2,4,8,16,32,64,128,256,512,1024
+  for (int i = 0; i < rs2; i++) {
+    printf("%d ", sbb2[i]); // expect: 1 2 4 8 16 32 64 128 256 512 1024
+    assert(sbb2[i] == r1[i]);
+  }
   printf("\n");
 }
diff --git a/sort_int_1bits.py b/sort_int_1bits.py
@@ -1,4 +1,5 @@
 # 1356. Sort Integers by The Number of 1 Bits
+from typing import List
 
 """
 given an integer array 'arr', sort the integers in the array in ascending
@@ -8,23 +9,17 @@ ascending order. return the array after sorting it.
 """
 
 
-class Solution(object):
-    def sortByBits(self, arr):
-        n = len(arr)
-        ans = [0] * n
-        for i in range(n):
-            ans[i] = self.count_bit(arr[i]) * 10001 + arr[i]
-        ans.sort()
-        for i in range(n):
-            ans[i] %= 10001
-        return ans
+class Solution:
+    def sortByBits(self, arr: List[int]) -> List[int]:
+        def weight(n):
+            w = 0
+            while n:
+                w += 1
+                n &= n - 1
+            return w
 
-    def count_bit(self, n):
-        res = 0
-        while n != 0:
-            res += n & 1
-            n >>= 1
-        return res
+        arr.sort(key=lambda x: (weight(x), x))
+        return arr
 
 
 if __name__ == "__main__":