Two Solutions | Bit Manipulation & DFA | Both O(n)
Solution 1 | Bit Manipulation:\n## Intuition\n\nWith each new bit, we can determine the new remainder by left-shifting the new bit onto the existing remainder a
# Solution 1 | Bit Manipulation:\n## Intuition\n\nWith each new bit, we can determine the new remainder by left-shifting the new bit onto the existing remainder and then computing the modulo of the resultant value. \n\nThis approach ensures that the length of the resulting value would remain at most 4 bits vs other bit manipulation approaches. This approach will work on an infinitely long input list regardless of language.\n\n## Approach\n<!-- Describe your approach to solving the problem. -->\nIncrement over each bit in the array and left shift that bit into the last remainder. \n\nMod the new by 5 and store it back into the remainder value.\n\nIf our remainder holds any value other that 0, the number is not divisible by 5.\n\n## Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1):\\ Ignoring\\ the\\ return\\ array$$\n## Python3\n```\nclass Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n        answer = []\n        remainder = 0\n\n        for num in nums:\n            remainder = (remainder << 1 | num) % 5\n            answer.append(not bool (remainder))\n\n        return answer\n```\n# C++\n```\nclass Solution {\npublic:\n    vector<bool> prefixesDivBy5(vector<int>& A) {\n        vector<bool> answer(A.size());\n        int remainder = 0;\n        \n        for(int i = 0; i < A.size(); i++) {\n            remainder = (remainder << 1 | A[i])  % 5;\n            answer[i] = !(bool)remainder;\n        }\n        return answer;\n    }\n};\n```\n# C\n```\nbool* prefixesDivBy5(int* nums, int numsSize, int* returnSize) {\n    bool* answer = (bool*)malloc(sizeof(bool) * numsSize);\n    int remainder = 0;\n    \n    *returnSize = numsSize;\n    for(int i = 0; i < numsSize; i++) {\n        remainder = (remainder << 1 | nums[i]) % 5;\n        answer[i] = !(bool)remainder;\n    }\n\n    return answer;\n}\n```\n\n---\n\n# Solution 2: DFA (Deterministic Finite Automaton):\n\n## Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs discussed above, since the new remainder can be obtained by left-shifting the new bit onto the old remainder, we can design a deterministic finite automaton (DFA) with state transitions to achieve this same result.\n\nGiven that there are five potential remainders (0-4), we can establish a DFA comprising five states. The transition table presented below illustrates the state transitions for this DFA.\n\n$$\n\\begin{array}{ccccc}\n\\text{Prev Rem (State)} & \\text{Shift Bit} & \\text{w/ Shift Bit} & \\text{New \\%5 Rem (New State)} \\\\\n\\hline\n0\\| 000 & \\text{0} & 0\\|0000 & 0\\|0000 \\\\\n0\\|000 & \\text{1} & 1\\|0001& 1\\|0001 \\\\\n1\\|001 & \\text{0} & 2\\|0010 & 2\\|0010 \\\\\n1\\|001 & \\text{1} & 3\\|0011& 3\\|0011 \\\\\n2\\|010 & \\text{0} & 4\\|0100 & 4\\|0100 \\\\\n2\\|010 & \\text{1} & 5\\|0101 & 0\\|0000 \\\\\n3\\|011 & \\text{0} & 6\\|0110 & 1\\|0001 \\\\\n3\\|011 & \\text{1} & 7\\|0111 & 2\\|0010 \\\\\n4\\|100 & \\text{0} & 8\\|1000 & 3\\|0011 \\\\\n4\\|100 & \\text{1} & 9\\|1001 & 4\\|0100 \\\\\n\\end{array}\n$$\n\n![image](https://assets.leetcode.com/users/images/52c005ba-ecda-4ac3-a358-3689a3ee8d47_1612570337.6115665.png)\n#####\n\n## Approach\n<!-- Describe your approach to solving the problem. -->\nWe can construct the above DFA using a 2D array.\nEach row represents the states (0-5), and each column represents the next state based on the recieved input (0 or 1).\n\nWe  can increment over the input array, and everytime the current state is 0, \'accept\' and append \'true\' onto the answer list otherwise \'reject\' and append \'false\'.\n\n\n## Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1):\\ Ignoring\\ the\\ return\\ array$$\n\n## Python3\n```\nclass Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n        answer = []\n        dfa = [[0,1], [2,3], [4,0], [1,2], [3,4]]\n        cur_state = 0\n        \n        for num in nums:\n            cur_state = dfa[cur_state][num]\n            answer.append(not bool(cur_state))\n        \n        return answer\n```\n\n## C++\n\n```\nclass Solution {\npublic:\n    vector<bool> prefixesDivBy5(vector<int>& A) {\n        vector<bool> answer(A.size());\n        int dfa[5][2] ={{0,1}, {2,3}, {4,0}, {1,2}, {3,4}};\n        int curState = 0;\n        \n        for(int i = 0; i < A.size(); i++) {\n            curState = dfa[curState][A[i]];\n            answer[i] = !(bool)curState;\n        }\n\n        return answer;\n    }\n};\n```\n\n## C\n```\nbool* prefixesDivBy5(int* nums, int numsSize, int* returnSize) {\n    bool* answer = (bool*)malloc(sizeof(bool) * numsSize);\n    int dfa[5][2] = {{0,1}, {2,3}, {4,0}, {1,2}, {3,4}};\n    int curState = 0;\n    \n    *returnSize = numsSize;\n    for(int i = 0; i < numsSize; i++) {\n        curState = dfa[curState][nums[i]];\n        answer[i] = !(bool)curState;\n    }\n\n    return answer;\n}\n```
['Bit Manipulation', 'C', 'Simulation', 'C++', 'Python3']