No of pairs ( a [ j ] >= a [ i ] ) with k numbers in range ( a [ i ] , a [ j ] ) that are divisible by x | C ++ 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 to check the above function ; function call to get the number of pairs
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countPairs ( int a [ ] , int n , int x , int k ) { sort ( a , a + n ) ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int d = ( a [ i ] - 1 ) / x ; int it1 = lower_bound ( a , a + n , max ( ( d + k ) * x , a [ i ] ) ) - a ; int it2 = lower_bound ( a , a + n , max ( ( d + k + 1 ) * x , a [ i ] ) ) - a ; ans += it2 - it1 ; } return ans ; } int main ( ) { int a [ ] = { 1 , 3 , 5 , 7 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int x = 2 , k = 1 ; cout << countPairs ( a , n , x , k ) ; return 0 ; }