LeetCode 1018. Binary Prefix Divisible By 5

[Woodyiiiiiii]

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation: 
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. 
Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: [1,1,1]
Output: [false,false,false]

Example 3:

Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]

Example 4:

Input: [1,1,1,0,1]
Output: [false,false,false,false,false]

Note:

1. 1 <= A.length <= 30000
2. A[i] is 0 or 1

---

这道题是easy难度，一开始我以为很简单，写出了以下做法：

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> res = new ArrayList<>();
        int n = A.length;
        if (n <= 0) return res;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum = sum * 2 + A[i];
            if (sum % 5 == 0) res.add(true);
            else res.add(false);
        }
        return res;
    }
}

然后发现“Wrong Answer”了...我检查了一遍，发现思路没有错，那么可能是溢出了，我改成long型也没有通过测试。

看了别人的做法，我才明白了一些：防止整数溢出，我们需要把数字sum限制在不溢出的范围内，同时保证能做是否能被整除5的判断——每次都对sum余5操作，这样sum被局限在0-4的范围内，当等于0的时候说明能被5整除。

主要思想是：假如数值一开始是8，那么8%5=3，而接下来的操作是乘2加1或0(假设下一位是1)，那么8数值被剔除的部分5，只需要做乘以2，又被%号剔除了，所以不影响3*2+1=7的结果，即可以这样看8=5+3, (3 +5) * 2 + 1。

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        ArrayList<Boolean> res = new ArrayList<>();
        int n = A.length;
        if (n <= 0) return res;
        int sum = 0;
        for (int a : A) {
            sum = (sum * 2 + a) % 5;
            if (sum == 0) res.add(true);
            else res.add(false);
        }
        return res;
    }
}

---

参考资料:

• https://leetcode.com/problems/binary-prefix-divisible-by-5/