leetcode_SAO/contests/
contest130.rs

1/// # 1018. Binary Prefix Divisible By 5
2/// 
3/// Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0]
4/// to A[i] interpreted as a binary number (from most-significant-bit to 
5/// least-significant-bit.) Return a list of booleans answer, where answer[i]
6/// is true if and only if N_i is divisible by 5.
7/// 
8/// ## Examples
9/// ### example1
10/// The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in 
11/// base-10.  Only the first number is divisible by 5, so answer[0] is true.
12/// 
13/// ```
14/// # use leetcode_SAO::contests::contest130::prefixes_div_by5;
15/// #
16/// let a = vec![0, 1, 1];
17/// assert_eq!(prefixes_div_by5(a), [true, false, false]);
18/// ```
19/// 
20/// ### example2
21/// ```
22/// # use leetcode_SAO::contests::contest130::prefixes_div_by5;
23/// #
24/// let a = vec![1, 1, 1];
25/// assert_eq!(prefixes_div_by5(a), [false, false, false]);
26/// ```
27/// 
28/// ### example3
29/// ```
30/// # use leetcode_SAO::contests::contest130::prefixes_div_by5;
31/// #
32/// let a = vec![0,1,1,1,1,1];
33/// assert_eq!(prefixes_div_by5(a), [true,false,false,false,true,false]);
34/// ```
35/// 
36/// ### example4
37/// ```
38/// # use leetcode_SAO::contests::contest130::prefixes_div_by5;
39/// #
40/// let a = vec![1,1,1,0,1];
41/// assert_eq!(prefixes_div_by5(a), [false,false,false,false,false]);
42/// ```
43/// 
44/// ## Input Range
45/// 1 <= A.length <= 30000
46/// A[i] is 0 or 1
47pub fn prefixes_div_by5(a: Vec<i32>) -> Vec<bool> {
48    let mut result = Vec::with_capacity(a.len());
49    
50    a.iter()
51        .fold(0i32, |N_i, &a_i| {
52            // use Congruence properties to prevent numberic overflow
53            let N_i = (N_i * 2 + a_i) % 5;
54            result.push(N_i == 0);
55            
56            N_i
57        });
58    
59    result
60}
leetcode_SAO/contests/contest130.rs

leetcode_SAO/contests/
contest130.rs
