𝗗𝗲𝘁𝗮𝗶𝗹𝗲𝗱 𝗘𝘅𝗽𝗹𝗮𝗻𝗮𝘁𝗶𝗼𝗻 | Python | C | 𝗢(𝗻) | DFA | Theory | Thought Process
\u2714 \uD835\uDDD7\uD835\uDDD8\uD835\uDDE7\uD835\uDDD4\uD835\uDDDC\uD835\uDDDF\uD835\uDDD8\uD835\uDDD7 \uD835\uDDD8\uD835\uDDEB\uD835\uDDE3\uD835\uDDDF\uD835\u
# \u2714 \uD835\uDDD7\uD835\uDDD8\uD835\uDDE7\uD835\uDDD4\uD835\uDDDC\uD835\uDDDF\uD835\uDDD8\uD835\uDDD7 \uD835\uDDD8\uD835\uDDEB\uD835\uDDE3\uD835\uDDDF\uD835\uDDD4\uD835\uDDE1\uD835\uDDD4\uD835\uDDE7\uD835\uDDDC\uD835\uDDE2\uD835\uDDE1 \n\nThis **Solution** will use the concept of **Finite Automaton**, and is similar to <ins>[this][1]</ins> answer. \n> \uD83D\uDC4D\uD83C\uDFFB  Those who are well aware of the term can quickly read the post. You will appreciate finding `Practical Application` of `Theory of Automata` \n> \n> \uD83D\uDE44  You haven\'t heard the term? Even you can continue reading! Slowly you will get everything. At last you can dub that you have `learnt new concept the hard way`.\n> \n> \uD83D\uDCDD You will appreciate unique thought process of solving the problem. Make sure to have pen-paper with you. Try to visualize.\n>\n> \uD83D\uDE09 <ins>Solution will slowly build-up `theory`, then we will quickly `analyze problem` and then `code` the thought-process. At last we will try to `optimize` the code.</ins> Last Section of post will take care of Edits and Reply to Comments/Doubts.\n\nWe will simulate a **[Deterministic Finite Automaton (DFA)][1]** that **accepts** Binary Representation of Integers which are divisible by 5, and we want to do this again and again for every substring from index `0` to index `i` \n\n> Now, by **accept**,  we mean that when we are done with scanning that particular sub-string, we should be in one of the multiple possible Final States.  \n<br>\n\n\n\n----------\n\n\n\n<br>\n\n# \uD83D\uDCD1 \uD835\uDDE7\uD835\uDDDB\uD835\uDDD8\uD835\uDDE2\uD835\uDDE5\uD835\uDDEC\n\n**Approach to Design DFA :** We need to divide the Binary Representation of Integer by 5, and track the remainder. If after consuming/scanning [From MSB to Current LSB, LSB will keep on changing] the entire sub-string, remainder is Zero, then we should end up in Final State [and note down `True`], and if remainder isn\'t zero we should be in Non-Final States [and note down `False`]\n\nNow, DFA is defined by **(Q,q\u2080,F,\u03A3,\u03B4)**. We will obtain these five components step-by-step.\n> Confused? Continue reading, you will enjoy the Journey. \uD83D\uDE0E\n\n\n1. **Q : Finite Set of States**    \nWe need to track remainder. On dividing any integer by `5`, we can get remainder as `0,1, 2, 3 or 4`. Hence, we will have Five States `Z, O, T, Th and F`  for each possible remainder. \n**Q={Z, O, T, Th, F}**  \nIf after scanning certain *part* of Binary String, we are in state `Z`, this means that integer defined from <ins>`Left to this part`</ins> will give remainder `Z`ero when divided by `5`. Similarly, `O` for remainder `O`ne, and so on.  \nNow, we can write these three states by [Euclidean Division Algorithm][2] as \n**Z** : 5`m`        \n**O**  : 5`m`+1        \n**T**  : 5`m`+2         \n**Th** : 5`m`+3        \n**F** : 5`m`+4    \nwhere `m` is Integer.\n<br>\n\n2. **q\u2080 : an initial/start state from set Q**  \nNow, start state can be thought in terms of empty string (`\u025B`). An `\u025B` directly gets into q\u2080.   \nWhat remainder does `\u025B` gives when divided by 5?    \nWe can append as many `0s` in left hand side of a *Binary Number*. In the similar fashion, we can append  `\u025B`  in left hand side of a *Binary String*. Thus,  `\u025B`  in left can be thought of as `0`. And `0` when divided by `5` gives remainder `0`. Hence,  `\u025B`  should end in State `Z`. But  `\u025B` ends up in q\u2080. <br>  \nThus, **q\u2080=Z**\n<br>\n\n3. **F : a set of accept states**   \nNow we want all strings which are divisible by 5, **or** which gives remainder 0 when divided by 5, **or** which after complete scanning should end up in state Z, and gets accepted. [`True`]\nHence, \n**F={Z}**\n<br>\n\n4. **\u03A3 : Alphabet (a finite set of input symbols)**  \nSince we are scanning/reading a Binary String. Hence,\n**\u03A3={0,1}**\n<br>\n\n5. **\u03B4 : Transition Function (\u03B4 : Q \xD7 \u03A3 \u2192 Q)** \nNow this \u03B4 tells us that if we are in state `x (in Q)` and next input to be scanned is `y (in \u03A3)`, then at which state `z (in Q)` should we go. <br>\n<ins>In context of this problem, if the string upto this point gives remainder `3/Th` when divided by `5`, and if we append `1` to string, then what remainder will resultant string give.</ins>  **The Primary Focus of this Problem.** Read This Line Again. \u2714\n<br>\nNow, this can be analyzed by observing *how magnitude of a binary string changes on appending 0 and 1*.<br>\n`a.` \nIn Decimal `(Base-10)`, if we add/append `0`, then magnitude gets multiplied by `10` . 53, on appending 0 it becomes 530  \nAlso, if we append 8 to decimal, then  Magnitude gets multiplied by `10`, and then we add `8` to multiplied magnitude.\n<br>`b.` \nIn **Binary (Base-2),** if we **add/append 0**, then magnitude gets multiplied by 2 (The Positional Weight of each Bit get multiplied by 2)  \n**Example :** (1010)<sub>2</sub> *[which is (10)<sub>10</sub>]*, on appending 0 it becomes (10100)<sub>2</sub> *[which is (20)<sub>10</sub>]*\nSimilarly, In **Binary**, if we **append 1**, then Magnitude gets multiplied by 2, and then we add 1.  \n**Example :** (10)<sub>2</sub> *[which is (2)<sub>10</sub>]*, on appending 1 it becomes (101)<sub>2</sub> *[which is (5)<sub>10</sub>]*\n<br>**Thus, we can say that for Binary String x,   \n`-` x0=2|x| \n`-` x1=2|x|+1\n[Key Formula of Problem]**\n<br>We will use these relation to analyze Five States [Read Carefully from <ins>this point</ins>  \uD83D\uDC4D\uD83C\uDFFB]\n<br>**Any string in `Z` can be written as `5m`**  \n  `-` On 0, it becomes `2(5m)`, which is `5(2m)`, nothing but state `Z`.  \n  `-` On 1, it becomes `2(5m)+1`, which is `5(2m)+1`, that is `O`.  *[This can be read as if a Binary String is presently divisible by 5, and we append 1, then resultant string will give remainder as 1]*   \n<br>**Any string in `O` can be written as `5m+1`**  \n  `-` On 0, it becomes `2(5m+1) = 10m+2`, which is `5(2m)+2`, state `T`.  \n  `-` On 1, it becomes `2(5m+1)+1 = 10m+3`, which is `5(2m)+3`, that is state `Th`.   \n<br>**Any string in `T` can be written as `5m+2`**\n  `-` On 0, it becomes `2(5m+2) = 10m+4`, which is `5(2m)+4`, state `F`.  \n  `-` On 1, it becomes `2(5m+2)+1 = 10m+5`, which is `5(2m+1)`, state `Z`.   *[If m is integer, so is (2m+1)]*     \n <br>**Any string in `Th` can be written as `5m+3`**  \n  `-` On 0, it becomes `2(5m+3) = 10m+6`, which is `5(2m+1)+1`, state `V`.  \n  `-` On 1, it becomes `2(5m+3)+1 = 10m+7`, which is `5(2m+1)+2`, that is state `T`.   \n<br>**Any string in `F` can be written as `5m+4`**  \n  `-` On 0, it becomes `2(5m+4) = 10m+8`, which is `5(2m+1)+3`, state `Th`.  \n  `-` On 1, it becomes `2(5m+4)+1 = 10m+9`, which is `5(2m+1)+4`, that is state `F`.   \n\n**Hence, the final DFA combining Everything (creating using [Tool](https://ivanzuzak.info/noam/webapps/fsm_simulator/))**  \n\n![image](https://assets.leetcode.com/users/images/6b6a317e-6943-43fa-b808-c388795582ed_1654124624.3723285.png)\n<br>\n\n\n\n----------\n\n\n\n<br>\n\n# \uD83D\uDDEF\uD835\uDDD4\uD835\uDDE1\uD835\uDDD4\uD835\uDDDF\uD835\uDDEC\uD835\uDDED\uD835\uDDDC\uD835\uDDE1\uD835\uDDDA \uD835\uDDE3\uD835\uDDE5\uD835\uDDE2\uD835\uDDD5\uD835\uDDDF\uD835\uDDD8\uD835\uDDE0 \uD835\uDDEE\uD835\uDDFB\uD835\uDDF1 \uD835\uDDE5\uD835\uDDD8\uD835\uDDDF\uD835\uDDD4\uD835\uDDE7\uD835\uDDDC\uD835\uDDE1\uD835\uDDDA \uD835\uDE04\uD835\uDDF6\uD835\uDE01\uD835\uDDF5 \uD835\uDDD7\uD835\uDDD9\uD835\uDDD4\n\n> `x\u1D62`  is the number whose binary representation is subarray `nums[0..i]` (from most-significant-bit to least-significant-bit). Return an *array of booleans* `answer` where `answer[i]` is `true` if  `x\u1D62` is divisible by 5.\n \n Thus, we have to simulate entire array `nums` on DFA, but after scanning every character, if it\'s in state `Z`, then we should append `True` in Answers, else append `False`.  \uD83D\uDE09\n \n**Examples:** \n- **[0,1,1]** \nIn State `Z` (Starting State), scan 0, go to `Z`, add `true`\nIn `Z`, scan 1, go to `O`, add `false`\nIn `O`, scan 1, go to `Th`, add `false`\n**Output :** `[true, false, false]`\n\n- **[1,1,1]** \nIn `Z`, scan 1, go to `O`, add `false`\nIn `O`, scan 1, go to `Th`, add `false`\nIn `Th`, scan 1, go to `T`, add `false`\n**Output :** `[false, false, false]`\n\n- **[1,0,1,0,1,1,1]** \nIn `Z`, scan 1, go to `O`, add `false`\nIn `O`, scan 0, go to `T`, add `false`\nIn `T`, scan 1, go to `Z`, add `true` [101, i. e. 5 is divisble by 5]\nIn `Z`, scan 0, go to `Z`, add `true` [1010 (Ten) is divisble by 5]\nIn `Z`, scan 1, go to `O`, add `false` \nIn `O`, scan 1, go to `Th`, add `false` \nIn `Th`, scan 1, go to `T`, add `false` \n**Output :** `[false, false, true, true, false, false, false]`\n\n<br>\n\n\n\n----------\n\n\n\n<br>\n\n# \uD83D\uDCBB \uD835\uDDE4\uD835\uDDE8\uD835\uDDDC\uD835\uDDD6\uD835\uDDDE-\uD835\uDDD6\uD835\uDDE2\uD835\uDDD7\uD835\uDDD8\nHere is the non-optimized code using the same concept. Comments to clarify things.\n\n**Python**\n```python\nclass Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:       \n\t\n        #To store transition Function. Key is Current State. Index of Value represents input symbol. \n\t\t#ELement at index represents Next State\n        D = {\'Z\':[\'Z\',\'O\'], \'O\':[\'T\',\'Th\'], \'T\':[\'F\',\'Z\'], \'Th\':[\'O\',\'T\'], \'F\':[\'Th\',\'F\']}\n        \n        #Will Store Current State\n        q = \'Z\'\n    \n        answer = []\n        \n        for i in nums:\n\t\t\n            answer.append(D[q][i]==\'Z\')\n            #Now D[q] is a List. i will be either 0 or 1, so is index of list. \n\t\t\t#We have to check if next state is Z or not.\n            \n            q = D[q][i]\n            #Go to Next State\n        \n        return answer\n``` \n\n\u23F3 **Time Complexity :** `O(n)` where `n` is number of elements in `nums`\n*[Assigning `D`,`q`, and `answer` is `O(1)`, and now `for` loop runs `n` times. Every Statement inside `for` loop is of `O(1)` ]*\n\n\u2328 **Space Complexity :** `O(n)` where `n` is number of elements in `nums`\n*[`D` and `q` will consume constant space. `answer` will store `n` elements, which depends on input. Although, since we are returning allocated memory, many text will claim Space Complexity to be `O(1)`]*\n\n<br>\n\n\n\n----------\n\n\n\n<br>\n\n# \uD83D\uDC68\uD83C\uDFFB\u200D\uD83D\uDCBB\uD835\uDDE2\uD835\uDDE3\uD835\uDDE7\uD835\uDDDC\uD835\uDDE0\uD835\uDDDC\uD835\uDDED\uD835\uDDDC\uD835\uDDE1\uD835\uDDDA/\uD835\uDDE9\uD835\uDDD4\uD835\uDDE5\uD835\uDDDC\uD835\uDDD4\uD835\uDDE7\uD835\uDDDC\uD835\uDDE2\uD835\uDDE1\uD835\uDDE6\nWe surely can optimize the code in both, time and space dimensions. Here are some pointers. We can combine multiple pointers to produce different variations. \uD83D\uDE0E\n\n- **Not consuming Extra Space** : This can be done by modifying  array in-place.\n```python        \n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:       \n        D = {\'Z\':[\'Z\',\'O\'], \'O\':[\'T\',\'Th\'], \'T\':[\'F\',\'Z\'], \'Th\':[\'O\',\'T\'], \'F\':[\'Th\',\'F\']}\n        cur = \'Z\'\n    \n        for i in range(len(nums)):\n            nxt = D[cur][nums[i]]\n            nums[i] = nxt==\'Z\'\n            cur = nxt\n        \n        return nums\n```\n\nUsing only one variable `cur`, we can have \n```python\ncur=D[cur][nums[i]]\nnums[i] = cur==\'Z\'\n```\n\n- Instead of using Alphabets for State [which represents Remainder], we can directly use Numeric Value of Remainder. Thinking Further, we can use **Arithmetic**  to replace Dictionary with List/Array. [Without Arithmetic, one can use 2D Array instead of Dictionary]\n```python\n        #Current State\n        q=0\n        \n        #Instead of using Dictionary, we can use List. Here\'s How.\n        \'\'\'\n        Our Dictionary looked like\n        D = {0 : [0,1], 1: [2,3], 2: [4,0], 3:[1,2], 4;[3,4]}\n\t\t\n\t\t#indexV (index of Value in Key-Value Pair) [which is a List] represents input symbol. \n\t\t#ELement at index represents Next State\n\t\t\n\t\t\n\t\t\n\t\t2D-Array will look like\n\t\tT = [ [0,1] , [2,3] , [4,0] , [1,2] , [3,4] ]\n    \n\t\n\t   Now, preparing 1-D Array. Writing only Values in List\n        L       = [0,1,   2,3,   4,0,  1,2,   3,4]\n        indexL  =  0 1    2 3    4 5   6 7    8 9\n        Key     =   0      1      2     3      4\n        \n        Noticed Any Pattern?\n        \n        I. From Key, we can get indexL (index of List) by Multiplying Key by 2, \n        and adding the indexV (which can be 0 or 1, input symbol)\n        \n                        OR\n                        \n        II. From Key, we can directly get element of List (instead of indexL)\n        by Multipling Key by 2, adding indexV and taking mod 5\n        \n        \n        Using Approach-I here\n        \n        \'\'\'\n        \n        #Transtition Function\n        L = [0,1,2,3,4,0,1,2,3,4]\n        \n        n = len(nums)\n        answer = [False]*n\n        \n        for i in range(n):\n            \n            #indexL will be multiplying current key/state by 2, and adding nums[i] (input)\n            #We want element at indexL, which will be next state.\n            q = L [2*q + nums[i] ]\n            \n            \n            #If Next State is Zero, it\'s negation will be True\n            if not q:\n                answer[i]=True\n        \n        return answer\n        \n```\n- We can modifiy many components of code\n```if not q: answer[i]=True``` can be written as ```answer[i] = q==0 ```\nAnd, ```q = L [2*q + nums[i] ]``` using bitwise operator can be written as ```q = L [q<<1 | nums[i] ]``` \n\n- Using `Approach-II` as mentioned in previous code comment, we can ultimately get rid of constant-sized list by using **Modular Arithmetic** and bit of **Bit-Manipulation**. More in Comments.\n ```python\n class Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n        #Current State\n        q=0\n        \n        #Instead of using Dictionary, we can use List. Here\'s How.\n        \'\'\'\n        Our Dictionary looked like\n        D = {0 : [0,1], 1: [2,3], 2: [4,0], 3:[1,2], 4;[3,4]}\n        \n        #indexV (index of Value in Key-Value Pair) [which is a List] represents input symbol. \n\t\t#ELement at index represents Next State\n        \n        Writing only Values in List\n        L       = [0,1,   2,3,   4,0,  1,2,   3,4]\n        Key     =   0      1      2     3      4\n        \n        From Key, we can directly get element of List\n        by Multipling Key by 2, adding indexV/input Symbol and taking mod 5.\n        This is concept of Modular Arithmetic\n        \n        Now, key multiplied by 2 will be Even. LSB of Even is 0. \n        Thus Even|1 increments number. Even|0 makes no change. (| is Bitwise OR)\n        Thus, instead of adding input Symbol, we will take OR.\n        This is Concept of Bit Manipulation\n        \n        And since we can get element of List, we don\'t have to allocate\n        space to List :)\n        \'\'\'\n        \n        #Transtition Function\n        \n        n = len(nums)\n        answer = [False]*n\n        \n        for i in range(n):\n            \n            #next State will be multiplying current key/state by 2, ORing nums[i] (input)\n            #Then taking mod 5\n            #q will always be from {0,1,2,3,4}\n            q = (q<<1 | nums[i])%5\n            \n            #If Next State is Zero, means Divisible. True.\n            answer[i]=q==0\n        \n        return answer\n        \n ```\n \n ---------- \n  \n# \uD83D\uDE0E \uD835\uDDD6\uD835\uDDE2\uD835\uDDE1\uD835\uDDD6\uD835\uDDDF\uD835\uDDE8\uD835\uDDE6\uD835\uDDDC\uD835\uDDE2\uD835\uDDE1\n\nHence, starting from the very theoretical basics, we have build DFA, Coded it, and Provided it\'s different variations. There are more than average comment in code to clarify each and every line. Solution in `python` is written in such a way that it can be converted to other languages easily. Here is one of the Final [but not claiming to be most optimized] Code, with `O(n)` Time Complexity and `O(1)` Space Complexity.\n\n**Python**\n\n```python\nclass Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n        q=0                \n        for i in range(len(nums)):\n            q = (q<<1 | nums[i])%5\n            nums[i]= q==0\n        \n        return nums\n```\n\nQuickly Converting \u2B50\n\n```c []\nbool* prefixesDivBy5(int* nums, int numsSize, int* returnSize)\n{\n    *returnSize=numsSize;\n    int q=0;\n\t\n\t//Using `answer`, as `int array` is different from demanded `bool array`\n    bool* answer=(bool *)malloc(numsSize*sizeof(bool));\n\t\n    for(register int i=0 ; i<numsSize; i++)\n    {\n        q = ((q<<1) | nums[i]) % 5;\n        answer[i] = (q==0);\n    }\n                \n    return answer;\n}\n```\n```python3 []\nclass Solution:\n    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n        q=0                \n        for i in range(len(nums)):\n            q = (q<<1 | nums[i])%5\n            nums[i]= q==0\n        \n        return nums\n```\n\n\n\n<br>\n\n- \u2B06\uFE0F If you have gained some insights, feel free to upvote. Button Below \n- \u2B50 Feel free to add to your Favorite Solutions by clicking on Star.\n- \uD83D\uDE15 If you are confused, or have some doubts, post comments.\n- \uD83D\uDCA1 Any mistake or Have another idea? Share in Comments. \n\n\n----\n\n\n# \uD83E\uDD16 \uD835\uDDD8\uD835\uDDF1\uD835\uDDF6\uD835\uDE01\uD835\uDE00/\uD835\uDDE5\uD835\uDDF2\uD835\uDDFD\uD835\uDDF9\uD835\uDE06\uD835\uDDF6\uD835\uDDFB\uD835\uDDF4 \uD835\uDE01\uD835\uDDFC \uD835\uDDE4\uD835\uDE02\uD835\uDDF2\uD835\uDDFF\uD835\uDDF6\uD835\uDDF2\uD835\uDE00\n\n\n**Isn\'t it too much for a `Easy` Problem?**\nWell, I guess it isn\'t too much. The solution tries to relate with `Theory of Computation`, a core subject offered in Computer Science Courses. The solution isn\'t tough. It slowly, and step-by-step tries to build widely submitted solution [as evident from Discussion]. It is written in such a way that even a novice can understand it. Hence, ideally it isn\'t too much.\n\n---------- \n  <br>\n  \n  [1]: https://stackoverflow.com/a/72594907/15845697\n  [2]: https://en.wikipedia.org/wiki/Euclidean_division#Division_theorem\n
['C', 'Python']