Find all pairs ( a , b ) in an array such that a % b = k | Utiltity function to find the divisors of n and store in vector v [ ] ; Vector is used to store the divisors ; If n is a square number , push only one occurrence ; Function to find pairs such that ( a % b = k ) ; Store all the elements in the map to use map as hash for finding elements in O ( 1 ) time . ; Print all the pairs with ( a , b ) as ( k , numbers greater than k ) as k % ( num ( > k ) ) = k i . e . 2 % 4 = 2 ; Now check for the current element as ' a ' how many b exists such that a % b = k ; find all the divisors of ( arr [ i ] - k ) ; Check for each divisor i . e . arr [ i ] % b = k or not , if yes then prthat pair . ; Clear vector ; Driver Code
import math as mt NEW_LINE def findDivisors ( n ) : NEW_LINE INDENT v = [ ] NEW_LINE for i in range ( 1 , mt . floor ( n ** ( .5 ) ) + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT if ( n / i == i ) : NEW_LINE INDENT v . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT v . append ( i ) NEW_LINE v . append ( n // i ) NEW_LINE DEDENT DEDENT DEDENT return v NEW_LINE DEDENT def printPairs ( arr , n , k ) : NEW_LINE INDENT occ = dict ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT occ [ arr [ i ] ] = True NEW_LINE DEDENT isPairFound = False NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( occ [ k ] and k < arr [ i ] ) : NEW_LINE INDENT print ( " ( " , k , " , " , arr [ i ] , " ) " , end = " ▁ " ) NEW_LINE isPairFound = True NEW_LINE DEDENT if ( arr [ i ] >= k ) : NEW_LINE INDENT v = findDivisors ( arr [ i ] - k ) NEW_LINE for j in range ( len ( v ) ) : NEW_LINE INDENT if ( arr [ i ] % v [ j ] == k and arr [ i ] != v [ j ] and occ [ v [ j ] ] ) : NEW_LINE INDENT print ( " ( " , arr [ i ] , " , " , v [ j ] , " ) " , end = " ▁ " ) NEW_LINE isPairFound = True NEW_LINE DEDENT DEDENT DEDENT DEDENT return isPairFound NEW_LINE DEDENT arr = [ 3 , 1 , 2 , 5 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE if ( printPairs ( arr , n , k ) == False ) : NEW_LINE INDENT print ( " No ▁ such ▁ pair ▁ exists " ) NEW_LINE DEDENT