1018. Binary Prefix Divisible By 5

class Solution:
    def prefixesDivBy5(self, A: List[int]) -> List[bool]:
        """tc O(N) sc O(1)
        main idea:  
        
        """
        for i in range(1,len(A)):
            A[i] += A[i-1] *2 % 5  # presum , note % 5 twice is to reduce the memory hold in caculation(prevent overflow) without affecting final result
        return [a%5==0 for a in A]

class Solution:
    def prefixesDivBy5(self, A: List[int]) -> List[bool]:
        res = []
        x = 0
        for a in A :
            x = x*2 + a  #x = x << 1 | a 
            if x %  5 == 0:
                res.append(True)
            else:
                res.append(False)
        return res