DDSA Solutions

1018. Binary Prefix Divisible By 5

EasyView on LeetCode
ArrayMath
Time: O(n)
Space: O(1)

Problem Overview

Track running binary number mod 5.

Intuition

Track running binary number mod 5. At each bit: num = (num*2 + bit) % 5.

Algorithm

  1. 1num = 0.
  2. 2For each bit: num = (num*2 + bit) % 5. Append num==0 to result.

Common Pitfalls

  • •Mod at every step prevents overflow.
1018.cs
C#
// Approach: Maintain running value mod 5; only the last 3 bits matter since 2^3 mod 5 cycles.
// Time: O(n) Space: O(1)

public class Solution
{
    public IList<bool> PrefixesDivBy5(int[] nums)
    {
        IList<bool> ans = new List<bool>();
        int curr = 0;

        foreach (int num in nums)
        {
            curr = (curr * 2 + num) % 5;
            ans.Add(curr % 5 == 0);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems