Dirichlet Principle: Pigeon hole principle

findAllPairWhichDiffMultipleIs.py

class circularQueue:
    def __init__(self,size,arr):
        # since python doesn`t have arrays i`m using list in place (by default a "list" is a linked list in python)
        self.arr = arr
        
        self.head=0
        self.tail=0
        self.size=size
    
    def next(self,ptr):
        return (ptr+1) % (self.size)
    
    def isEmpty(self):
        return self.head == self.tail
    
    def isFull(self):
        return self.head == self.next(self.tail) 
        
    def push(self,e):
        if self.arr[self.tail] is None:
            self.arr[self.tail]=e
        if not self.isFull():
            self.tail = self.next(self.tail)
        
    def pop(self):
        if not self.isEmpty():
            self.arr[self.head]=None
            if self.isFull() and self.next(self.tail) != self.head:
                self.tail = self.next(self.tail)
            self.head=self.next(self.head)
    
    def peek(self,ptr):
        return self.arr[ptr]
    
    def findFirstPairWhichDiffMultipleIs(self,multiple):
        self.tail = self.next(self.head)
        
        print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
        
        while(not self.isEmpty()):
            print(f'{self.peek(self.head)}-{self.peek(self.tail)}={abs(self.peek(self.head)-self.peek(self.tail))} % {multiple}')
            
            if abs(self.peek(self.head) - self.peek(self.tail)) % multiple == 0:
                return [self.peek(self.head),self.peek(self.tail)]
            if self.isFull():
                self.pop()
            self.tail = self.next(self.tail)
    
    def findFirstPairWhichDiffMultipleIs(self,multiple):
        self.tail = self.next(self.head)
        
        print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
        
        while(not self.isEmpty()):
            print(f'{self.peek(self.head)}-{self.peek(self.tail)}={abs(self.peek(self.head)-self.peek(self.tail))} % {multiple}')
            
            if abs(self.peek(self.head) - self.peek(self.tail)) % multiple == 0:
                return [self.peek(self.head),self.peek(self.tail)]
            if self.isFull():
                self.pop()
            self.tail = self.next(self.tail)
            
    def findFirstPairWhichDiffMultipleIs(self,multiple):
        self.tail = self.next(self.head)
        iterations = 0
        
        print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
        
        while(not self.isEmpty()):
            iterations = iterations+1
            print(f'{self.peek(self.head)}-{self.peek(self.tail)}={abs(self.peek(self.head)-self.peek(self.tail))} % {multiple}')
            
            if abs(self.peek(self.head) - self.peek(self.tail)) % multiple == 0:
                return [self.peek(self.head),self.peek(self.tail)],iterations
                
            if self.isFull() or self.peek(self.next(self.tail)) is None:
                self.pop()
                
                if not self.isEmpty():
                    self.tail = self.next(self.head)
                    
                print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
                continue
            self.tail = self.next(self.tail)
    
    def findAllPairWhichDiffMultipleIs(self,multiple):
        stack = []
        iterations = 0
        self.tail = self.next(self.head)
        
        print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
        
        while(not self.isEmpty()):
            iterations = iterations+1
            print(f'{self.peek(self.head)}-{self.peek(self.tail)}={abs(self.peek(self.head)-self.peek(self.tail))} % {multiple}')
            
            if abs(self.peek(self.head) - self.peek(self.tail)) % multiple == 0:
                stack.append([self.peek(self.head),self.peek(self.tail)])
                
            if self.isFull() or self.peek(self.next(self.tail)) is None:
                self.pop()
                
                if not self.isEmpty():
                    self.tail = self.next(self.head)
                    
                print(f' {self.arr}\n head={self.head}\n tail={self.tail}\n')
                continue
            self.tail = self.next(self.tail)
        
        return stack,iterations
    
sequence = [30,71,102,103,250]
N = len(sequence)
queue = circularQueue(N,sequence)
pairs1, iter1 = queue.findFirstPairWhichDiffMultipleIs(N-1)
pairs2, iter2 = queue.findAllPairWhichDiffMultipleIs(N-1)
print(f'find first pair took {iter1} iterations found: {pairs1}\n')
print(f'find all pairs (worst case) took {iter2} iterations found: {pairs2}\n')

Execute on online python compiler