Find all pairs ( a , b ) in an array such that a % b = k | C ++ program to find all pairs 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 print that pair . ; Clear vector ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findDivisors ( int n ) { vector < int > v ; for ( int i = 1 ; i <= sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { if ( n / i == i ) v . push_back ( i ) ; else { v . push_back ( i ) ; v . push_back ( n / i ) ; } } } return v ; } bool printPairs ( int arr [ ] , int n , int k ) { unordered_map < int , bool > occ ; for ( int i = 0 ; i < n ; i ++ ) occ [ arr [ i ] ] = true ; bool isPairFound = false ; for ( int i = 0 ; i < n ; i ++ ) { if ( occ [ k ] && k < arr [ i ] ) { cout << " ( " << k << " , ▁ " << arr [ i ] << " ) ▁ " ; isPairFound = true ; } if ( arr [ i ] >= k ) { vector < int > v = findDivisors ( arr [ i ] - k ) ; for ( int j = 0 ; j < v . size ( ) ; j ++ ) { if ( arr [ i ] % v [ j ] == k && arr [ i ] != v [ j ] && occ [ v [ j ] ] ) { cout << " ( " << arr [ i ] << " , ▁ " << v [ j ] << " ) ▁ " ; isPairFound = true ; } } v . clear ( ) ; } } return isPairFound ; } int main ( ) { int arr [ ] = { 3 , 1 , 2 , 5 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 2 ; if ( printPairs ( arr , n , k ) == false ) cout << " No ▁ such ▁ pair ▁ exists " ; return 0 ; }