Skip to content

Latest commit

 

History

History
69 lines (59 loc) · 1.53 KB

1018. Binary Prefix Divisible By 5.md

File metadata and controls

69 lines (59 loc) · 1.53 KB
Raw

1018. Binary Prefix Divisible By 5

leetcode-cn Daily Challenge on January 14th, 2021.

Difficulty : Easy

Related Topics : Array

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

Solution

  • mine
    • Java
      • Runtime: 2 ms, faster than 100.00%, Memory Usage: 39.8 MB, less than 43.14% of Java online submissions 
        public List<Boolean> prefixesDivBy5(int[] A) {
    List<Boolean> res = new ArrayList<>(A.length);
    int t = 0;
    for(int a : A){
        t = (t << 1) + a;
        t = t % 5;
        res.add(t == 0);
    }
    return res;
}