Find all pairs (a, b) in an array such that a % b = k

Last Updated : 15 Sep, 2023

Given an array with distinct elements, the task is to find the pairs in the array such that a % b = k, where k is a given integer.

Examples :

Input  :  arr[] = {2, 3, 5, 4, 7}   
              k = 3
Output :  (7, 4), (3, 4), (3, 5), (3, 7)
7 % 4 = 3
3 % 4 = 3
3 % 5 = 3
3 % 7 = 3

A Naive Solution is to make all pairs one by one and check their modulo is equal to k or not. If equals to k, then print that pair.

Implementation:

C++

// C++ implementation to find such pairs 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find pair such that (a % b = k) 
bool printPairs(int arr[], int n, int k) 
{ 
    bool isPairFound = true; 
  
    // Consider each and every pair 
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < n; j++) { 
            // Print if their modulo equals to k 
            if (i != j && arr[i] % arr[j] == k) { 
                cout << "(" << arr[i] << ", "
                     << arr[j] << ")"
                     << " "; 
                isPairFound = true; 
            } 
        } 
    } 
  
    return isPairFound; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = { 2, 3, 5, 4, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 3; 
  
    if (printPairs(arr, n, k) == false) 
        cout << "No such pair exists"; 
  
    return 0; 
} 

Java

// Java implementation to find such pairs 
  
class Test { 
    // method to find pair such that (a % b = k) 
    static boolean printPairs(int arr[], int n, int k) 
    { 
        boolean isPairFound = true; 
  
        // Consider each and every pair 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 
                // Print if their modulo equals to k 
                if (i != j && arr[i] % arr[j] == k) { 
                    System.out.print("(" + arr[i] + ", " + arr[j] + ")"
                                     + " "); 
                    isPairFound = true; 
                } 
            } 
        } 
  
        return isPairFound; 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        int arr[] = { 2, 3, 5, 4, 7 }; 
        int k = 3; 
  
        if (printPairs(arr, arr.length, k) == false) 
            System.out.println("No such pair exists"); 
    } 
} 

Python3

# Python3 implementation to find such pairs 
  
# Function to find pair such that (a % b = k) 
def printPairs(arr, n, k): 
  
    isPairFound = True
  
    # Consider each and every pair 
    for i in range(0, n): 
      
        for j in range(0, n): 
          
            # Print if their modulo equals to k 
            if (i != j and arr[i] % arr[j] == k): 
              
                print("(", arr[i], ", ", arr[j], ")", 
                                 sep = "", end = " ") 
                isPairFound = True
              
    return isPairFound 
  
# Driver Code 
arr = [2, 3, 5, 4, 7] 
n = len(arr)  
k = 3
if (printPairs(arr, n, k) == False): 
    print("No such pair exists") 
  
#  

C#

// C# implementation to find such pair 
using System; 
  
public class GFG { 
      
    // method to find pair such that (a % b = k) 
    static bool printPairs(int[] arr, int n, int k) 
    { 
        bool isPairFound = true; 
  
        // Consider each and every pair 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++)  
            { 
                // Print if their modulo equals to k 
                if (i != j && arr[i] % arr[j] == k) 
                { 
                    Console.Write("(" + arr[i] + ", " 
                                + arr[j] + ")" + " "); 
                    isPairFound = true; 
                } 
            } 
        } 
  
        return isPairFound; 
    } 
  
    // Driver method 
    public static void Main() 
    { 
        int[] arr = { 2, 3, 5, 4, 7 }; 
        int k = 3; 
  
        if (printPairs(arr, arr.Length, k) == false) 
            Console.WriteLine("No such pair exists"); 
    } 
} 
  
// This code is contributed by Sam007 

PHP

<?php 
// PHP implementation to 
// find such pairs 
  
// Function to find pair 
// such that (a % b = k) 
function printPairs($arr, $n, $k) 
{ 
    $isPairFound = true; 
  
    // Consider each and every pair 
    for ($i = 0; $i < $n; $i++)  
    { 
        for ( $j = 0; $j < $n; $j++)  
        { 
            // Print if their modulo 
            // equals to k 
            if ($i != $j && $arr[$i] %  
                            $arr[$j] == $k)  
            { 
                echo "(" , $arr[$i] , ", ", 
                       $arr[$j] , ")", " "; 
                $isPairFound = true; 
            } 
        } 
    } 
  
    return $isPairFound; 
} 
  
// Driver Code 
$arr = array(2, 3, 5, 4, 7); 
$n = sizeof($arr); 
$k = 3; 
  
if (printPairs($arr, $n, $k) == false) 
    echo "No such pair exists"; 
  
// This code is contributed by ajit 
?> 

Javascript

<script> 
    // Javascript implementation to find such pair 
      
    // method to find pair such that (a % b = k) 
    function printPairs(arr, n, k) 
    { 
        let isPairFound = true; 
    
        // Consider each and every pair 
        for (let i = 0; i < n; i++) { 
            for (let j = 0; j < n; j++)  
            { 
                // Print if their modulo equals to k 
                if (i != j && arr[i] % arr[j] == k) 
                { 
                    document.write("(" + arr[i] + ", " + arr[j] + ")" + " "); 
                    isPairFound = true; 
                } 
            } 
        } 
    
        return isPairFound; 
    } 
      
    let arr = [ 2, 3, 5, 4, 7 ]; 
    let k = 3; 
  
    if (printPairs(arr, arr.length, k) == false) 
      document.write("No such pair exists"); 
  
</script>

Output

(3, 5) (3, 4) (3, 7) (7, 4)

Time Complexity : O(n²)
Auxiliary Space: O(1)

An Efficient solution is based on below observations :

If k itself is present in arr[], then k forms a pair with all elements arr[i] where k < arr[i]. For all such arr[i], we have k % arr[i] = k.
For all elements greater than or equal to k, we use the following fact.

   If arr[i] % arr[j] = k, 
   ==> arr[i] = x * arr[j] + k
   ==> (arr[i] - k) = x * arr[j]
  We find all divisors of (arr[i] - k)
  and see if they are present in arr[].

To quickly check if an element is present in the array, we use hashing.

Implementation:

C++

// C++ program to find all pairs such that 
// a % b = k. 
#include <bits/stdc++.h> 
using namespace std; 
  
// Utility function to find the divisors of 
// n and store in vector v[] 
vector<int> findDivisors(int n) 
{ 
    vector<int> v; 
  
    // Vector is used to store  the divisors 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If n is a square number, push 
            // only one occurrence 
            if (n / i == i) 
                v.push_back(i); 
            else { 
                v.push_back(i); 
                v.push_back(n / i); 
            } 
        } 
    } 
    return v; 
} 
  
// Function to find pairs such that (a%b = k) 
bool printPairs(int arr[], int n, int k) 
{ 
    // Store all the elements in the map 
    // to use map as hash for finding elements 
    // in O(1) time. 
    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++) { 
        // Print all the pairs with (a, b) as 
        // (k, numbers greater than k) as 
        // k % (num (> k)) = k i.e. 2%4 = 2 
        if (occ[k] && k < arr[i]) { 
            cout << "(" << k << ", " << arr[i] << ") "; 
            isPairFound = true; 
        } 
  
        // Now check for the current element as 'a' 
        // how many b exists such that a%b = k 
        if (arr[i] >= k) { 
            // find all the divisors of (arr[i]-k) 
            vector<int> v = findDivisors(arr[i] - k); 
  
            // Check for each divisor i.e. arr[i] % b = k 
            // or not, if yes then print that pair. 
            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; 
                } 
            } 
  
            // Clear vector 
            v.clear(); 
        } 
    } 
  
    return isPairFound; 
} 
  
// Driver program 
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; 
} 

Java

// Java program to find all pairs such that 
// a % b = k. 
  
import java.util.HashMap; 
import java.util.Vector; 
  
class Test { 
    // Utility method to find the divisors of 
    // n and store in vector v[] 
    static Vector<Integer> findDivisors(int n) 
    { 
        Vector<Integer> v = new Vector<>(); 
  
        // Vector is used to store  the divisors 
        for (int i = 1; i <= Math.sqrt(n); i++) { 
            if (n % i == 0) { 
                // If n is a square number, push 
                // only one occurrence 
                if (n / i == i) 
                    v.add(i); 
                else { 
                    v.add(i); 
                    v.add(n / i); 
                } 
            } 
        } 
        return v; 
    } 
  
    // method to find pairs such that (a%b = k) 
    static boolean printPairs(int arr[], int n, int k) 
    { 
        // Store all the elements in the map 
        // to use map as hash for finding elements 
        // in O(1) time. 
        HashMap<Integer, Boolean> occ = new HashMap<>(); 
        for (int i = 0; i < n; i++) 
            occ.put(arr[i], true); 
  
        boolean isPairFound = false; 
        for (int i = 0; i < n; i++) { 
            // Print all the pairs with (a, b) as 
            // (k, numbers greater than k) as 
            // k % (num (> k)) = k i.e. 2%4 = 2 
            if (occ.get(k) && k < arr[i]) { 
                System.out.print("(" + k + ", " + arr[i] + ") "); 
                isPairFound = true; 
            } 
  
            // Now check for the current element as 'a' 
            // how many b exists such that a%b = k 
            if (arr[i] >= k) { 
                // find all the divisors of (arr[i]-k) 
                Vector<Integer> v = findDivisors(arr[i] - k); 
  
                // Check for each divisor i.e. arr[i] % b = k 
                // or not, if yes then print that pair. 
                for (int j = 0; j < v.size(); j++) { 
                    if (arr[i] % v.get(j) == k && arr[i] != v.get(j) && occ.get(v.get(j))) { 
                        System.out.print("(" + arr[i] + ", "
                                         + v.get(j) + ") "); 
                        isPairFound = true; 
                    } 
                } 
  
                // Clear vector 
                v.clear(); 
            } 
        } 
  
        return isPairFound; 
    } 
  
    // Driver method 
    public static void main(String args[]) 
    { 
        int arr[] = { 3, 1, 2, 5, 4 }; 
        int k = 2; 
  
        if (printPairs(arr, arr.length, k) == false) 
            System.out.println("No such pair exists"); 
    } 
} 

Python3

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

C#

// C# program to find all pairs  
// such that a % b = k.  
using System; 
using System.Collections.Generic; 
  
class GFG 
{ 
// Utility method to find the divisors  
// of n and store in vector v[]  
public static List<int> findDivisors(int n) 
{ 
    List<int> v = new List<int>(); 
  
    // Vector is used to store  
    // the divisors  
    for (int i = 1;  
             i <= Math.Sqrt(n); i++) 
    { 
        if (n % i == 0) 
        { 
            // If n is a square number,  
            // push only one occurrence  
            if (n / i == i) 
            { 
                v.Add(i); 
            } 
            else
            { 
                v.Add(i); 
                v.Add(n / i); 
            } 
        } 
    } 
    return v; 
} 
  
// method to find pairs such 
// that (a%b = k)  
public static bool printPairs(int[] arr, 
                              int n, int k) 
{ 
    // Store all the elements in the  
    // map to use map as hash for  
    // finding elements in O(1) time.  
    Dictionary<int,  
               bool> occ = new Dictionary<int,  
                                          bool>(); 
    for (int i = 0; i < n; i++) 
    { 
        occ[arr[i]] = true; 
    } 
  
    bool isPairFound = false; 
    for (int i = 0; i < n; i++) 
    { 
        // Print all the pairs with (a, b) as  
        // (k, numbers greater than k) as  
        // k % (num (> k)) = k i.e. 2%4 = 2  
        if (occ[k] && k < arr[i]) 
        { 
            Console.Write("(" + k + ", " +  
                           arr[i] + ") "); 
            isPairFound = true; 
        } 
  
        // Now check for the current element 
        // as 'a' how many b exists such that  
        // a%b = k  
        if (arr[i] >= k) 
        { 
            // find all the divisors of (arr[i]-k)  
            List<int> v = findDivisors(arr[i] - k); 
  
            // Check for each divisor i.e.  
            // arr[i] % b = k or not, if 
            // yes then print that pair.  
            for (int j = 0; j < v.Count; j++) 
            { 
                if (arr[i] % v[j] == k &&  
                    arr[i] != v[j] && occ[v[j]]) 
                { 
                    Console.Write("(" + arr[i] + 
                                  ", " + v[j] + ") "); 
                    isPairFound = true; 
                } 
            } 
  
            // Clear vector  
            v.Clear(); 
        } 
    } 
  
    return isPairFound; 
} 
  
// Driver Code  
public static void Main(string[] args) 
{ 
    int[] arr = new int[] {3, 1, 2, 5, 4}; 
    int k = 2; 
  
    if (printPairs(arr, arr.Length, k) == false) 
    { 
        Console.WriteLine("No such pair exists"); 
    } 
} 
} 
  
// This code is contributed by Shrikant13 

Javascript

<script> 
  
// JavaScript program to find all pairs such that 
// a % b = k.     
      
    // Utility method to find the divisors of 
    // n and store in vector v[] 
    function findDivisors(n) 
    { 
        let v = []; 
   
        // Vector is used to store  the divisors 
        for (let i = 1; i <= Math.sqrt(n); i++)  
        { 
            if (n % i == 0) { 
                // If n is a square number, push 
                // only one occurrence 
                if (n / i == i) 
                    v.push(i); 
                else { 
                    v.push(i); 
                    v.push(Math.floor(n / i)); 
                } 
            } 
        } 
        return v; 
    } 
      
    // method to find pairs such that (a%b = k) 
    function printPairs(arr,n,k) 
    { 
        // Store all the elements in the map 
        // to use map as hash for finding elements 
        // in O(1) time. 
        let occ = new Map(); 
        for (let i = 0; i < n; i++) 
            occ.set(arr[i], true); 
   
        let isPairFound = false; 
        for (let i = 0; i < n; i++) { 
            // Print all the pairs with (a, b) as 
            // (k, numbers greater than k) as 
            // k % (num (> k)) = k i.e. 2%4 = 2 
            if (occ.get(k) && k < arr[i]) { 
                document.write("(" + k + ", " +  
                arr[i] + ") "); 
                isPairFound = true; 
            } 
   
            // Now check for the current element as 'a' 
            // how many b exists such that a%b = k 
            if (arr[i] >= k) { 
                // find all the divisors of (arr[i]-k) 
                let v = findDivisors(arr[i] - k); 
   
                // Check for each divisor  
                // i.e. arr[i] % b = k 
                // or not, if yes then  
                // print that pair. 
                for (let j = 0; j < v.length; j++)  
                { 
                    if (arr[i] % v[j] == k && 
                    arr[i] != v[j] && 
                    occ.get(v[j]))  
                    { 
                        document.write("(" + arr[i] + ", "
                                         + v[j] + ") "); 
                        isPairFound = true; 
                    } 
                } 
   
                // Clear vector 
                v=[]; 
            } 
        } 
   
        return isPairFound; 
    } 
      
    // Driver method 
    let arr=[3, 1, 2, 5, 4 ]; 
    let k = 2; 
    if (printPairs(arr, arr.length, k) == false) 
            document.write("No such pair exists"); 
      
  
// This code is contributed by unknown2108 
  
</script> 

Output

(2, 3) (2, 5) (5, 3) (2, 4)

Time Complexity: O(n* sqrt(max)) where max is the maximum element in the array.
Auxiliary Space: O(n)

This article is contributed by Aarti_Rathi and Sahil Chhabra.

Smitha Dinesh Semwal

Improve

Sort elements by frequency | Set 4 (Efficient approach using hash)

Group words with same set of characters

Easy problems on Hashing

Intermediate problems on Hashing

Hard problems on Hashing

Find all pairs (a, b) in an array such that a % b = k

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?