1018. Binary Prefix Divisible By 5

EasyView on LeetCode

Array Math

Time: O(n)

Space: O(1)

Intuition

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

Algorithm

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

Common Pitfalls

•Mod at every step prevents overflow.

1018.cs

// 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?