Algorithm

Problem Name: 1018. Binary Prefix Divisible By 5

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

You are given a binary array nums (0-indexed).

We define xi as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).

  • For example, if nums = [1,0,1], then x0 = 1, x1 = 2, and x2 = 5.

Return an array of booleans answer where answer[i] is true if xi is divisible by 5.

 

Example 1:

Input: nums = [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: nums = [1,1,1]
Output: [false,false,false]

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
    public List prefixesDivBy5(int[] A) {
        List list = new ArrayList<>();

        int currSum = 0;
        for (int i = 0; i  <  A.length; i++) {
            currSum = 2 * currSum + A[i];
            currSum %= 5;
            list.add(currSum % 5 == 0);
        }

        return list;
    }
}
.
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [0,1,1]

Output

x
–
+
cmd
[true,false,false]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const prefixesDivBy5 = function(A) {
    const res = []
    let pre = 0
    const len = A.length
    for(let i = 0; i  <  len; i++) {
      pre = (pre % 100) * 2 + A[i]
      res.push(pre % 5 === 0 ? true : false)
    }
    return res
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [0,1,1]

Output

x
–
+
cmd
[true,false,false]

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def prefixesDivBy5(self, A: List[int]) -> List[bool]:
        num = 0
        for i in range(len(A)):
            num = (num << 1) + A[i]
            A[i] = num % 5 == 0
        return A
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,1,1]

Output

x
–
+
cmd
[false,false,false]

#4 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _1018_BinaryPrefixDivisibleBy5
    {
        public IList < bool> PrefixesDivBy5(int[] A)
        {
            var results = new List(A.Length);
            var current = 0;
            foreach (var digit in A)
            {
                current = (current * 2 + digit) % 5;
                results.Add(current == 0);
            }

            return results;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,1,1]

Output

x
–
+
cmd
[false,false,false]
Advertisements

Demonstration

Previous
#1017 Leetcode Convert to Base -2 Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1019 Leetcode Next Greater Node In Linked List Solution in C, C++, Java, JavaScript, Python, C# Leetcode