Find All Pairs (a, b) In An Array Such That a % b = k

Introduction 📖

In the data structure, hashing is a technique of mapping a large part of data into small tables using a hashing function. We can also call it the message digest function. To uniquely identify a specific item from the collection of similar items, we use this technique of ‘Hashing’. 

In this blog, we will see the problem statement to find all pairs (a, b) in an array such that a % b = k and try to solve it using hashing with proper explanation, algorithm, and complexities.

Must Recommended Topic, Hash Function in Data Structure.

Problem Statement❓

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

This means we are given an array with a distinct element, and our task is to find the pairs of elements of a given array such that they satisfy the condition ‘a%b=k’, where ‘k’ is a given integer.

Sample Input

array[] = {5, 4, 6, 7, 3}
k = 3

Sample Output

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

Pictorial Explanation

Let's look at the pictorial explanation of the problem statement: To find all pairs (a, b) in an array such that a % b = k.

The given five pairs are the output when a % b = k is true.

Algorithm🧑🏻‍💻

👉🏻 At first, we have to declare a map and set one of its arguments as a boolean. 
 

👉🏻 Store all the values of the given array with "true" boolean values into the map by traversing the original array.
 

👉🏻 Define a boolean variable with the name ‘foundPair’ and set its value to "false".
 

👉🏻 Traverse the given array from ‘0’ to ‘n-1’, where ‘n’ is the array's length.

• Now we have to check if ‘k’ has an entry in the map and whether ‘k’ is smaller than the current array element or not. If true, print the ‘k’ and the array element value. Then set the boolean value to "true".
• Check if the value of ‘k’ is less than or equal to the current element of the array. If "true", create a vector and then find all the divisors of the array[i]-k value and store it into the vector. 
• Now traverse the vector we created in the previous step and we’ve to check if that element of a vector and the element of the array are pair that satisfies the given condition when modulo is done.
• Print the vector and the current array element and set the Boolean value to "true".
   

👉🏻 Return ‘foundPair’.

Implementation In C++💻

C++ code for the problem statement find all pairs (a, b) in an array such that a % b = k.

#include<math.h>
#include <unordered_map>
#include<iostream>
#include<vector>
using namespace std;

vector<int> findPossibleDiv(int n)
{
   vector<int> vecDiv;
   for (int j = 1; j <= sqrt(n); j++)
   {
       if (n % j == 0)
       {
           if (n / j == j)
               vecDiv.push_back(j);
           else
           {
               vecDiv.push_back(j);
               vecDiv.push_back(n / j);
           }
       }
   }
   return vecDiv;
}

bool pairModulousK(int array[], int n, int k)
{
   unordered_map<int, bool> MAP;
   for (int i = 0; i < n; i++)
       MAP[array[i]] = true;
   bool foundPair = false;
   for (int i = 0; i < n; i++)
   {
       if (MAP[k] && k < array[i])
       {
           cout << "(" << k << ", " << array[i] << ") ";
           foundPair = true;
       }
       if (array[i] >= k)
       {
           vector<int> vec = findPossibleDiv(array[i] - k);
           for (int j = 0; j < vec.size(); j++)
           {
               if (array[i] % vec[j] == k && array[i] != vec[j] && MAP[vec[j]])
               {
                   cout << "(" << array[i] << ", "<< vec[j] << ") ";
                   foundPair = true;
               }
           }
           vec.clear();
       }
   }
   return foundPair;
}

int main()
{
   int array[] = {5, 4, 6, 7, 3};
   int n = sizeof(array) / sizeof(array[0]);
   int k = 3;
   if (pairModulousK(array, n, k) == false)
       cout << "There is no such pair.";
   return 0;
}

Output -

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

You can also read about the Longest Consecutive Sequence.

Implementation In Java💻

Java code for the problem statement find all pairs (a, b) in an array such that a % b = k.

import java.util.HashMap;
import java.util.Vector;
 
class Test {
    static Vector<Integer> findTheDivisors(int n)
    {
        Vector<Integer> v = new Vector<>();
 
        for (int j = 1; j <= Math.sqrt(n); j++) 
        {
            if (n % j == 0) 
            {
                if (n / j == j)
                    v.add(j);
                else 
                {
                    v.add(j);
                    v.add(n / j);
                }
            }
        }
        return v;
    }
    
    static boolean printThePairs(int array[], int n, int k)
    {
        HashMap<Integer, Boolean> occ = new HashMap<>();
        for (int i = 0; i < n; i++)
            occ.put(array[i], true);
 
        boolean foundPair = false;
        for (int i = 0; i < n; i++) 
        {
            if (occ.get(k) && k < array[i]) 
            {
                System.out.print("(" + k + ", " + array[i] + ") ");
                foundPair = true;
            }
 
            if (array[i] >= k) 
            {
                Vector<Integer> v = findTheDivisors(array[i] - k);
 
                for (int j = 0; j < v.size(); j++) 
                {
                    if (array[i] % v.get(j) == k && array[i] != v.get(j) && occ.get(v.get(j))) 
                    {
                        System.out.print("(" + array[i] + ", "
                                         + v.get(j) + ") ");
                        foundPair = true;
                    }
                }
                v.clear();
            }
        }
        return foundPair;
    }
 
    public static void main(String args[])
    {
        int array[] = {5, 4, 6, 7, 3};
        int k = 3;
 
        if (printThePairs(array, array.length, k) == false)
            System.out.println("There is no such pair exists.");
    }
}
 

Output -

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

Implementation In Python💻

Python code for the problem statement find all pairs (a, b) in an array such that a % b = k.

import math as mt
 
def findTheDivisors(n):
    v = []
    for i in range(1, mt.floor(n**(.5)) + 1):
        if (n % i == 0):
            
            if (n / i == i):
                v.append(i)
            else:
                v.append(i)
                v.append(n // i)
    return v
 
def printThePairs(array, n, k):
 
    occ = dict()
    for i in range(n):
        occ[array[i]] = True
 
    foundPair = False
 
    for i in range(n):
        if (occ[k] and k < array[i]):
            print("(", k, ",", array[i], ")", end = " ")
            foundPair = True
 
        if (array[i] >= k):
            v = findTheDivisors(array[i] - k)
            for j in range(len(v)):
                if (array[i] % v[j] == k and
                    array[i] != v[j] and
                    occ[v[j]]):
                    print("(", array[i], ",", v[j],
                                      ")", end = " ")
                    foundPair = True
    return foundPair
array = [5, 4, 6, 7, 3]
n = len(array)
k = 3
 
if (printThePairs(array, n, k) == False):
    print("There is no such pair exists.")

Output -

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

Check out this array problem - Merge 2 Sorted Arrays

Complexities of Algorithm🎯

The time and space complexity of the given solution for the problem statement to find all pairs (a, b) in an array such that a % b = k are given below.

Time Complexity

The time complexity is O (n * sqrt(max)) where ‘max’ is the maximum element of the array.

We used the following fact for all the elements that are greater than or equal to k-

If arr[i] % arr[j] = k, 

   ==> arr[i] = x * arr[j] + k

   ==> (arr[i] - k) = x * arr[j]

We found the divisor of (array[i] - k) and checked if they are present in array[] by using hashing.

Space Complexity

The space complexity is O(n), where ‘n’ is the length of the given array. We need this space to store the element in the hash map.

Frequently Asked Questions🤔

What is hashing?

In the data structure, hashing is a technique of mapping a large part of data into small tables using a hashing function.

What is an array?

An array stores similar data type elements and has a fixed size. It stores elements in the contagious memory location, which means there is no space between the elements of an array in the memory location.

What is modulo?

In number theory, it is a symbol/operator (%) used to find the modulus of a number. Modulus is the remainder we get on dividing a number with another number.

What are all pairs (a, b) in an array {5, 4, 6, 7, 3} such that a % b = k where k = 2?

The pairs that satisfy the condition are (5, 3) (6, 4) (7, 5).

What is Boolean?

A data type called boolean has two possible values to assign, which are also called truth values that are "true" and "false".

Conclusion

In this blog, we went through the solution to the problem statement to find all pairs (a, b) in an array such that a % b = k using hashing. We also discussed the Algorithm of the solution and then understood the code and its complexities if you would like to learn more, check out our articles on Count quadruples from four sorted arrays whose sum is equal to a given value x and Count Divisible Pairs in an Array.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Happy Learning Ninja!