Sliding Window Divisible

sliding_window_divisible.py

from collections import deque


class SlidingWindowDivisible:
    """
    Test whether the product of a sliding window is divisible by a given number
    """
    def __init__(self, k: int):
        self.k = k
        self.queue = deque()
        self.product = 1
        self.count_zeros = 0

    def add(self, x: int):
        self.queue.append(x)
        if x == 0:
            self.count_zeros += 1
        else:
            self.product *= x

        if len(self.queue) > self.k:
            head = self.queue.popleft()
            if head == 0:
                self.count_zeros -= 1
            else:
                self.product //= head

    def is_divisible_by(self, p: int):
        if len(self.queue) == 0:
            return False  # or raise exception here, should clarify with interviewer
        if p == 0:
            if self.count_zeros > 0:
                return False  # or raise exception here, should clarify with interviewer
            return True
        else:
            if self.count_zeros > 0:
                return True
            return self.product % p == 0


# some test cases
if __name__ == "__main__":
    k = 3
    swd = SlidingWindowDivisible(k)
    swd.add(6)
    print(swd.is_divisible_by(3))
    print(swd.is_divisible_by(2))
    print(swd.is_divisible_by(7))
    swd.add(0)
    print(swd.is_divisible_by(7))
    swd.add(3)
    print(swd.is_divisible_by(8))
    swd.add(5)
    print(swd.is_divisible_by(8))
    swd.add(2)
    print(swd.is_divisible_by(7))
    print(swd.is_divisible_by(30))
    print(swd.is_divisible_by(0))