No of pairs ( a [ j ] >= a [ i ] ) with k numbers in range ( a [ i ] , a [ j ] ) that are divisible by x | Python3 program to calculate the number pairs satisfying th condition ; function to calculate the number of pairs ; traverse through all elements ; current number 's divisor ; use binary search to find the element after k multiples of x ; use binary search to find the element after k + 1 multiples of x so that we get the answer bu subtracting ; the difference of index will be the answer ; Driver code ; function call to get the number of pairs
import bisect NEW_LINE def countPairs ( a , n , x , k ) : NEW_LINE INDENT a . sort ( ) NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT d = ( a [ i ] - 1 ) // x NEW_LINE it1 = bisect . bisect_left ( a , max ( ( d + k ) * x , a [ i ] ) ) NEW_LINE it2 = bisect . bisect_left ( a , max ( ( d + k + 1 ) * x , a [ i ] ) ) NEW_LINE ans += it2 - it1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 3 , 5 , 7 ] NEW_LINE n = len ( a ) NEW_LINE x = 2 NEW_LINE k = 1 NEW_LINE print ( countPairs ( a , n , x , k ) ) NEW_LINE DEDENT