Count all distinct pairs with difference equal to k | A sorting based program to count pairs with difference k ; Standard binary search function ; Returns count of pairs with difference k in arr [ ] of size n . ; Sort array elements ; Pick a first element point ; Driver program
#include <iostream> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; int binarySearch ( int arr [ ] , int low , int high , int x ) { if ( high >= low ) { int mid = low + ( high - low ) / 2 ; if ( x == arr [ mid ] ) return mid ; if ( x > arr [ mid ] ) return binarySearch ( arr , ( mid + 1 ) , high , x ) ; else return binarySearch ( arr , low , ( mid - 1 ) , x ) ; } return -1 ; } int countPairsWithDiffK ( int arr [ ] , int n , int k ) { int count = 0 , i ; sort ( arr , arr + n ) ; for ( i = 0 ; i < n - 1 ; i ++ ) if ( binarySearch ( arr , i + 1 , n - 1 , arr [ i ] + k ) != -1 ) count ++ ; return count ; } int main ( ) { int arr [ ] = { 1 , 5 , 3 , 4 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; cout << " Count ▁ of ▁ pairs ▁ with ▁ given ▁ diff ▁ is ▁ " << countPairsWithDiffK ( arr , n , k ) ; return 0 ; }