leetcode

commit e0e5e33e5a335d61db2bf35c7d13bc60bd104fe7
parent 6acfe62c4bb62dbf5cd70427ae325aa81ac507b5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 20 May 2026 08:39:29 +0300

2657. find the prefix common array of the two arrays

Diffstat:
M
find_prefix_common_arr.c
 | 
43
+++++++++++++++++++++++--------------------
M
find_prefix_common_arr.py
 | 
24
++++++++++--------------

2 files changed, 33 insertions(+), 34 deletions(-)
diff --git a/find_prefix_common_arr.c b/find_prefix_common_arr.c
@@ -12,32 +12,35 @@
 
 int *findThePrefixCommonArray(int *A, int ASize, int *B, int BSize,
                               int *returnSize) {
-  int *ans = (int *)malloc(ASize * sizeof(int)), cnt = 0;
-  int *vis = (int *)malloc((ASize + 1) * sizeof(int));
+  int *ans = (int *)malloc(ASize * sizeof(int));
+  *returnSize = ASize;
+  long long a = 0, b = 0;
   for (int i = 0; i < ASize; i++) {
-    if (++vis[A[i]] == 2)
-      cnt++;
-    if (++vis[B[i]] == 2)
-      cnt++;
-    ans[i] = cnt;
+    a |= (1LL << A[i]);
+    b |= (1LL << B[i]);
+    long long ab = a & b;
+    ans[i] = __builtin_popcountll(ab);
   }
-  free(vis);
-  *returnSize = ASize;
   return ans;
 }
 
 int main() {
-  int a1[] = {1, 2, 3, 4}, b1[] = {3, 1, 2, 4}, rs1;
-  int a2[] = {2, 3, 1}, b2[] = {3, 1, 2}, rs2;
-  int *ftpca1 =
-      findThePrefixCommonArray(a1, ARRAY_SIZE(a1), b1, ARRAY_SIZE(b1), &rs1);
-  int *ftpca2 =
-      findThePrefixCommonArray(a2, ARRAY_SIZE(a2), b2, ARRAY_SIZE(b2), &rs2);
-  for (int i = 0; i < rs1; i++)
-    printf("%d ", ftpca1[i]); // expect: 0 2 3 4
+  int a1[] = {1, 2, 3, 4}, b1[] = {3, 1, 2, 4}, r1[] = {0, 1, 3, 4};
+  int a2[] = {2, 3, 1}, b2[] = {3, 1, 2}, r2[] = {0, 1, 3};
+  int rs1, *ftpca1 = findThePrefixCommonArray(a1, ARRAY_SIZE(a1), b1,
+                                              ARRAY_SIZE(b1), &rs1);
+  int rs2, *ftpca2 = findThePrefixCommonArray(a2, ARRAY_SIZE(a2), b2,
+                                              ARRAY_SIZE(b2), &rs2);
+  for (int i = 0; i < rs1; i++) {
+    printf("%d ", ftpca1[i]);
+    assert(ftpca1[i] == r1[i]);
+  }
   printf("\n");
-  for (int i = 0; i < rs2; i++)
-    printf("%d ", ftpca2[i]); // expect: 0 1 3
+  for (int i = 0; i < rs2; i++) {
+    printf("%d ", ftpca2[i]);
+    assert(ftpca2[i] == r2[i]);
+  }
   printf("\n");
-  free(ftpca1), free(ftpca2);
+  free(ftpca1);
+  free(ftpca2);
 }
diff --git a/find_prefix_common_arr.py b/find_prefix_common_arr.py
@@ -10,20 +10,16 @@ exactly once.
 """
 
 
-class Solution(object):
-    def findThePrefixCommonArray(self, A, B):
-        """
-        :type A: List[int]
-        :type B: List[int]
-        :rtype: List[int]
-        """
-        ans, vis, cnt = [], 0, 0
-        for ab in zip(A, B):
-            for a in ab:
-                if (1 << a) & vis:
-                    cnt += 1
-                vis |= 1 << a
-            ans.append(cnt)
+class Solution:
+    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
+        n = len(A)
+        ans = [0] * n
+        a, b = 0, 0
+        for i in range(n):
+            a |= 1 << A[i]
+            b |= 1 << B[i]
+            ab = a & b
+            ans[i] = ab.bit_count()
         return ans