leetcode

commit 441a61937d0fe800e01d78999850affb39e8e88b
parent b8cd5fabf3ef2254280eef58a35fdcfe23271ee6
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 23 Nov 2025 22:19:34 -0700

1018. binary prefix divisible by 5

Diffstat:
A
binary_prefix_div_5.c
 | 
35
+++++++++++++++++++++++++++++++++++
A
binary_prefix_div_5.py
 | 
23
+++++++++++++++++++++++

2 files changed, 58 insertions(+), 0 deletions(-)
diff --git a/binary_prefix_div_5.c b/binary_prefix_div_5.c
@@ -0,0 +1,35 @@
+// 1018. Binary Prefix Divisible By 5
+#include "leetcode.h"
+
+/*
+ * you are given a binary array 'nums'. we define 'x_i' as the number whose
+ * binary representation is the subarray 'nums[0..i]' from (msb to lsb). return
+ * an array of booleans 'answer' where 'answer[i]' is 'true' if 'x_i' is divible
+ * by 5
+ */
+
+bool *prefixesDivBy5(int *nums, int numsSize, int *returnSize) {
+  bool *ans = (bool *)malloc(numsSize * sizeof(bool));
+  *returnSize = numsSize;
+  int msb = 0;
+  for (int i = 0; i < numsSize; i++) {
+    msb = ((msb << 1) + nums[i]);
+    msb -= (-(msb >= 5) & 5);
+    ans[i] = !msb;
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {0, 1, 1}, n2[] = {1, 1, 1}, rs1, rs2;
+  bool *pdb51 = prefixesDivBy5(n1, ARRAY_SIZE(n1), &rs1);
+  bool *pdb52 = prefixesDivBy5(n2, ARRAY_SIZE(n2), &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", pdb51[i]); // expect: 1 0 0
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", pdb52[i]); // expect: 0 0 0
+  printf("\n");
+  free(pdb51);
+  free(pdb52);
+}
diff --git a/binary_prefix_div_5.py b/binary_prefix_div_5.py
@@ -0,0 +1,23 @@
+# 1018. Binary Prefix Divisible By 5
+
+"""
+you are given a binary array 'nums'. we define 'x_i' as the number whose
+binary representation is the subarray 'nums[0..i]' from (msb to lsb). return
+an array of booleans 'answer' where 'answer[i]' is 'true' if 'x_i' is divible
+by 5
+"""
+
+
+class Solution(object):
+    def prefixesDivBy5(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: List[bool]
+        """
+        return (msb := 0) or [((msb := ((msb << 1) + i) % 5) == 0) for i in nums]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.prefixesDivBy5(nums=[0, 1, 1]))
+    print(obj.prefixesDivBy5(nums=[1, 1, 1]))