Binary Prefix Divisible By 5 – Java/C++ Coding Exercise

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 <= A.length <= 30000
A[i] is 0 or 1

The algorithm is to iteratively accumulate the binary value (convert binary to decimal). As the array may be larger than 32 elements, which may overflow the 32-bit integer, we need to module 5 to keep the number under control.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> r = new ArrayList<>();
        int num = 0;
        for (int x: A) {
            num = ((num << 1) + x) % 5;
            r.add(num % 5 == 0);
        }        
        return r;
    }
}

class Solution {
    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> r = new ArrayList<>();
        int num = 0;
        for (int x: A) {
            num = ((num << 1) + x) % 5;
            r.add(num % 5 == 0);
        }        
        return r;
    }
}

We use logical shift <<1 to perform multiplication by two. The values are appended to the List (ArrayList) in Java.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> result;
        int x = 0;
        for (const auto y: A) {
            x = ((x << 1) + y) % 5;
            result.push_back(x % 5 == 0);
        }
        return result;
    }
};

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        vector<bool> result;
        int x = 0;
        for (const auto y: A) {
            x = ((x << 1) + y) % 5;
            result.push_back(x % 5 == 0);
        }
        return result;
    }
};

C++ uses vector.push_back to add an element to the vector (List). Both implementations are O(N) in both time and space.

–EOF (The Ultimate Computing & Technology Blog) —