Detailed explanation for mod calculation and equation (with super simple Java solution)
Java solution\n\njava\nclass Solution {\n    public List<Boolean> prefixesDivBy5(int[] A) {\n        List<Boolean> result = new ArrayList<>();\n        int r = 
**Java solution**\n\n```java\nclass Solution {\n    public List<Boolean> prefixesDivBy5(int[] A) {\n        List<Boolean> result = new ArrayList<>();\n        int r = 0;\n        for (int bit : A) {\n            r = (r * 2 + bit) % 5;\n            result.add(r % 5 == 0);\n        }\n        return result;\n    }\n}\n```\n\nThis question is similar to question 1015.  Assume we have the numer 0111, then we will check 0, 01, 011, 0111. For each number, we can carry the result to the next one through mod calculations, so we don\'t need to calculate the entire number again and again. The induction rule is `next = pre * 2 + lastBit`, for example, `0111 = 011 * 2 + 1`. Here\'s the prove:  \n```\n011  = 2^2 * 0 + 2^1 * 1 + 2^0 * 1 = 3\n0111 = 011 * 2 + 2^0 * 1 (the extra bit added at the end, either 0 or 1) \n     = (2^2 * 0 + 2^1 * 1 + 2^0 * 1) * 2 + 2^0 * 1\n     = 2^3 * 0 + 2^2 * 1 + 2^1 * 1 + 2^0 * 1\n     = 7\n```\nSince we always append the extra digit (0 or 1) at the end, which is multiplied by 2^0 = 1. Because multiplying by one could be ignored, we will simply add the extra digit at the end. Eventually, we have `next = pre * 2 + bit`.  \n\nNext, we need to record the remainder of the number rather than the whole number, as it will go overflow quickly. Here\'s how:\n\nIn general, we know that `(a + b) % k = (a % k + b % k ) % k` and in this question, we already get `next = pre * 2 + bit`.  \n\nFirst we assume:  \n```\nn % k = r\nn = m * k + r; \n```\nthen we can have:  \n```\n2n + lastBit = 2(mk + r) + lastBit\n2n + lastBit = 2mk + 2r + lastBit; \n(2n + lastBit) % k = (2r + lastBit) % k;\n```\nTherefore we know that calculation based on the number itself, `n`, and it\'s remainder, `r`, is the same. In other words, we don\'t have to do `next = pre * 2 + bit`, but rather `remainderOfNext = remainderOfPre * 2 + bit`
[]