[Java/Python 3] 7/1 liners - left shift, bitwise or, and mod.
Since A includes only 0s and 1s, we can imitate binary operations.\n\njava\n    public List<Boolean> prefixesDivBy5(int[] A) {\n        int k = 0;\n        List
Since A includes only `0s` and `1s`, we can imitate binary operations.\n\n```java\n    public List<Boolean> prefixesDivBy5(int[] A) {\n        int k = 0;\n        List<Boolean> ans = new ArrayList<>();\n        for (int a : A) {\n            k = (k << 1 | a) % 5; // left shift k by 1 bit and plus current element a is the binary number.\n            ans.add(k == 0); \n        }\n        return ans;\n    }\n```\n```python\n    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n        ans, b = [], 0\n        for a in A:\n            b = b << 1 | a\n            ans.append(b % 5 == 0)\n        return ans\n```\nUse `itertools.accumulate` to make the above 1 liner:\n```python\n    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n        return [x % 5 == 0 for x in itertools.accumulate(A, lambda a, b: a << 1 | b)]\n```\n**Analysis:**\n\nTime & space: O(n), where n = A.length;\n\n**Q & A:**\n\nQ:\nwhy do we need to mod 5 there?\nA: \nThe problem ask if the binary numbers are divisible by 5.\nAlso, mod 5 in each iteration will prevent potential int overflow.\n\nQ: \ncan you give me the explanation for why after mod 5 the value of k plus a can still represent the original value \uFF1F\nA:\n\nRewrite original code as follows, ignore the overflow test cases.\n```\n    public List<Boolean> prefixesDivBy5(int[] A) {\n        int[] k = new int[A.length + 1];\n        List<Boolean> ans = new ArrayList<>();\n        for (int i = 0; i < A.length; ++i) {\n            k[i + 1] = (k[i] << 1 | a); // left shift k by 1 bit and plus current element a is the binary number.\n            ans.add(k[i + 1] % 5 == 0); \n        }\n        return ans;\n    }\n```\n```\n\ni = 0,\n```\nLet F0 = k[0 + 1] / 5,\n    r0  = k[0 + 1] % 5,\nDenote k[0 + 1] (= A[0]) = 5 * F0 + r0, \n       k[0 + 1] % 5 = r0\n\nsimilarly,\n```\ni = 1,\n```\nk[1 + 1] = 2 * (5 * F0 + r0) + A[1] \n             = 2 * 5 * F0 + (**2 * r0 + A[1]**)\n\t\t     = 2 * 5 * F0 + (5 * F1 + r1)\nk[1 + 1] % 5 = **(2 * r0 + A[1]) % 5**\n                    = r1\n```\ni = 2,\n```\nk[2 + 1] = 2 * (2 * 5 * F0 + (5 * F1 + r1)) + A[2] \n             = (4 * 5 * F0 + 2 * 5 * F1) + (**2 * r1 + A[2]**)\n             = 5  * (4 * F0 + 2 * F1) + (5 * F2 + r2)\nk[2 + 1] % 5 =  (**2 * r1 + A[2]**) % 5\n                    = r2\n\nrepeat the above till the end of the array...\n\nLook at the bold part of the derivation, we can draw a conclusion that **ONLY the remainders such as r<sub>0</sub>,r<sub>1</sub>,r<sub>2</sub>, ...,r<sub>i</sub>..., count; While the part divisible by `5`, like `5 * (4 * F0 + 2 * F1),5 * F1,5 * (4 * F0 + 2 * F1),5 * F2`, does NOT matter.** \nThat is consistent with the original 1st Java code. Let me know if it answers your question.\n\n----\n\nFor more bit shift operations practice and solution, refer to [1290. Convert Binary Number in a Linked List to Integer](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/discuss/451815/javapython-3-simulate-binary-operations/434516)
[]