1.
Introduction 📖
2.
Problem Statement❓
2.1.
Sample Input
2.2.
Sample Output
2.3.
Pictorial Explanation
3.
Algorithm🧑🏻‍💻
4.
Implementation In C++💻
5.
Implementation In Java💻
6.
Implementation In Python💻
7.
Complexities of Algorithm🎯
7.1.
Time Complexity
7.2.
Space Complexity
8.
8.1.
What is hashing?
8.2.
What is an array?
8.3.
What is modulo?
8.4.
What are all pairs (a, b) in an array {5, 4, 6, 7, 3} such that a % b = k where k = 2?
8.5.
What is Boolean?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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)

## 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)
else
{
}
}
}
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.

### 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 -

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!

Live masterclass