Binary Prefix Divisible By 5 - Array - Easy - LeetCode

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:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
 public class PrefixesDivBy5Soln
 {
 public IList<bool> PrefixesDivBy5(int[] A)
 {
 if (A == null || A.Length <= 0) return null;
 int num = 0;
 var list = new List<bool>();
 foreach (var i in A) 
 {
 num = (num * 2 + i) % 5;
 if (num == 0)
 {
 list.Add(true);
 }
 else
 {
 list.Add(false);
 }
 }
 return list;
 }
 }
}

Time Complexity: O(n)

Space Complexity: O(1)

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
 [TestClass]
 public class PrefixesDivBy5SolnTests
 {
 [TestMethod]
 public void PrefixesDivBy5Soln_First()
 {
 var arr = new int[] { 0, 1, 1 };
 var expected = new bool[] { true, false, false };

 var res = new PrefixesDivBy5Soln().PrefixesDivBy5(arr);
 AreEqual(expected, res);
 }

 [TestMethod]
 public void PrefixesDivBy5Soln_Second()
 {
 var arr = new int[] { 1, 1, 1 };
 var expected = new bool[] { false, false, false };

 var res = new PrefixesDivBy5Soln().PrefixesDivBy5(arr);
 AreEqual(expected, res);
 }

 [TestMethod]
 public void PrefixesDivBy5Soln_Third()
 {
 var arr = new int[] { 0, 1, 1, 1, 1, 1 };
 var expected = new bool[] { true, false, false, false, true, false };

 var res = new PrefixesDivBy5Soln().PrefixesDivBy5(arr);
 AreEqual(expected, res);
 }

 [TestMethod]
 public void PrefixesDivBy5Soln_Fourth()
 {
 var arr = new int[] { 1, 1, 1, 0, 1 };
 var expected = new bool[] { false, false, false, false, false };

 var res = new PrefixesDivBy5Soln().PrefixesDivBy5(arr);
 AreEqual(expected, res);
 }

 [TestMethod]
 public void PrefixesDivBy5Soln_Fifth()
 {
 var arr = new int[] { 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1 };
 var expected = new bool[] { false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, true, true, true, true, false };

 var res = new PrefixesDivBy5Soln().PrefixesDivBy5(arr);
 AreEqual(expected, res);
 }

 private void AreEqual(bool[] res, IList<bool> output)
 {
 Assert.AreEqual(res.Length, output.Count);
 for (int i = 0; i < res.Length; i++)
 {
 Assert.AreEqual(res[i], output[i]);
 }
 }
 }
}