Table of Contents
Problem Statement
The problem “Find all pairs (a, b) in an array such that a % b = k” states that you are given an array of integers and an integer value called k. The problem statement asks to find out the pair in such a way that that x % y = k (given value) in an array.
Example
arr[] = {3, 4, 7, 5, 6 }
k = 3(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)
Explanation
These 4 pairs have been confirmed when a % b = k is true.
arr[]={2, 3, 5, 1},
k = 2(2, 3) (2, 5) (5, 3)
Explanation
These 3 pairs have been confirmed when a % b = k is true.
Algorithm
- Declare a map and select one of its arguments as a Boolean.
- Traverse the original array and store all the values of the array with true Boolean value into the map.
- Set any Boolean variable to say pairCheck to false.
- Traverse the array from 0 to n-1(n is the length of the array).
- Check if the given k value has an entry in a map and also k is smaller than the current array element. If true, then print the value k and also that array element and set that Boolean value to true.
- Check if the k is less than or equal to the current array element.
- If true then create a vector and find all the divisors of arr[i]-k value and store it into the vector.
- Traverse that vector and check if that element of vector and array element are pair which satisfies the condition when modulo is done.
- Print the vector and current array element and set the Boolean value to true.
- Return pairCheck.
Explanation
Given an array of integers and an integer value k. Find the pair in such a way that when we perform a modulo operation on a pair (x, y) such that x % y = k, then we need to print that pair, we have to do this with whole integer array. Find all those pairs which give the value k when we perform a modulo operation on a number x % y. For this, we are going to use one of the collections or STL called vector and map.
Put all of the array elements into the map and mark all of them with a “true” Boolean value. We need to initialize a Boolean variable called pairCheck to false. We are going to update it when we find the correct pair. then we are going to traverse the array now. And check if the given k value is present in a map or not. Also if k is less than the current array element. Then we just print that pair. Because when we divide small number by bigger number it will leave the remainder as a small number.
If the above condition becomes false, then we check if the current element is greater than k. If true, then we need to declare a vector where we pass the difference of current array element and k, which will return the vector in which the pairs possible values are returned. We are going to pick each of the value and check if current array element modulo returned value in the vector gives the remainder k or not. If it is true then print the pair and mark the pairCheck value as true, which means we found at least one pair. Proceed with further value with the same steps and print all the possible results.
Code
Implementation in C++ to find all pairs (a, b) in an array such that a % b = k
#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>
using namespace std;
vector<int> findPossibleDiv(int n)
{
vector<int> vecDiv;
for (int i = 1; i <= sqrt(n); i++)
{
if (n % i == 0)
{
if (n / i == i)
vecDiv.push_back(i);
else
{
vecDiv.push_back(i);
vecDiv.push_back(n / i);
}
}
}
return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
unordered_map<int, bool> MAP;
for (int i = 0; i < n; i++)
MAP[arr[i]] = true;
bool pairCheck = false;
for (int i = 0; i < n; i++)
{
if (MAP[k] && k < arr[i])
{
cout << "(" << k << ", " << arr[i] << ") ";
pairCheck = true;
}
if (arr[i] >= k)
{
vector<int> vec = findPossibleDiv(arr[i] - k);
for (int j = 0; j < vec.size(); j++)
{
if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
{
cout << "(" << arr[i] << ", "<< vec[j] << ") ";
pairCheck = true;
}
}
vec.clear();
}
}
return pairCheck;
}
int main()
{
int arr[] = { 3, 4, 7, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
if (pairModulousK(arr, n, k) == false)
cout << "No such pair exists";
return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)
Java code to find all pairs (a, b) in an array such that a % b = k
import java.util.HashMap;
import java.util.Vector;
class PairModuloK
{
public static Vector<Integer> findPossibleDiv(int n)
{
Vector<Integer> vecDiv = new Vector<>();
for (int i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
if (n / i == i)
vecDiv.add(i);
else
{
vecDiv.add(i);
vecDiv.add(n / i);
}
}
}
return vecDiv;
}
public static boolean pairModulousK(int arr[], int n, int k)
{
HashMap<Integer, Boolean> MAP = new HashMap<>();
for (int i = 0; i < n; i++)
MAP.put(arr[i], true);
boolean pairCheck = false;
for (int i = 0; i < n; i++)
{
if (MAP.get(k) && k < arr[i])
{
System.out.print("(" + k + ", " + arr[i] + ") ");
pairCheck = true;
}
if (arr[i] >= k)
{
Vector<Integer> vec = findPossibleDiv(arr[i] - k);
for (int j = 0; j < vec.size(); j++)
{
if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
{
System.out.print("(" + arr[i] + ", "
+ vec.get(j) + ") ");
pairCheck = true;
}
}
vec.clear();
}
}
return pairCheck;
}
public static void main(String args[])
{
int arr[] = {3, 4, 7, 6, 5};
int k = 3;
if (pairModulousK(arr, arr.length, k) == false)
System.out.println("No such pair exists");
}
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)
Complexity Analysis
Time Complexity
O(n* sqrt(max)) where “max” is the maximum element in the array. This time complexity was achieved because we used
Space Complexity
O(n) where “n” is the number of elements in the array. This space is required for storing the elements in the map.