Blogs Hub

Binary Prefix Divisible By 5 - Array - Easy - LeetCode - MiniTV

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]);
            }
        }
    }
}