Print all distinct pairs with given difference in array
The problem you're addressing is to find all distinct pairs in an array that have a given difference 'k'. These pairs are defined as two elements whose absolute difference is equal to the given value 'k'. The objective is to create an algorithm that identifies these pairs efficiently and displays them as output.
Problem Statement
Given an array of integers and a difference 'k', the task is to find all pairs of distinct elements whose absolute difference is equal to 'k'.
Example
Let's take an array arr = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4] and 'k' as 3.
Pairs with a difference of 3: {4, 1}, {5, 2}, {8, 5}.
Idea to Solve
- Create an auxiliary array to keep track of whether a given index in the original array should be considered or not (to handle duplicate elements).
- Iterate through the original array, marking the indices of duplicate elements in the auxiliary array.
- Iterate through the array again, considering only non-duplicate elements, and for each element 'arr[i]', check if 'arr[i] + k' or 'arr[i] - k' exists in the array. If either of them does, then a pair with the required difference is found.
Algorithm
- Create a function
difference(arr[], size, k):- Initialize an auxiliary array
auxiliaryof sizesizewith all elements set to 0. - Detect duplicates and mark corresponding indices in
auxiliary. - Iterate through the array and find pairs with the desired difference using the auxiliary array.
- Initialize an auxiliary array
Pseudocode
function difference(arr[], size, k):
if size <= 0:
return
auxiliary[size] = {0, 0, ..., 0} // Initialize auxiliary array
for i from 0 to size - 1:
for j from i + 1 to size - 1:
if arr[i] == arr[j]:
auxiliary[j] = 1 // Mark duplicate index
display "Pairs of difference", k
for i from 0 to size - 1:
if auxiliary[i] == 1:
continue
for j from i + 1 to size - 1:
if auxiliary[j] == 1:
continue
if abs(arr[i] - arr[j]) == k:
display "{", arr[i], ",", arr[j], "} "
main():
arr = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4]
size = size of arr
print_array(arr, size)
difference(arr, size, 3)Code Solution
//C Program
//Print all distinct pairs with given difference in array
#include <stdio.h>
#include <stdlib.h>
void difference(int arr[],int size,int k)
{
if(size<=0)
{
return;
}
//For check duplicates nodes
int auxiliary[size];
//Find Duplicates
for (int i = 0; i < size; ++i)
{
for (int j = i+1; j < size; ++j)
{
if(arr[i]==arr[j])
{
//When get repeated element
auxiliary[j]=1;
}
}
}
printf("\nPairs of difference %d\n",k);
for (int i = 0; i < size; ++i)
{
if(auxiliary[i]==1)
{
continue;
}
for (int j = i+1; j < size; ++j)
{
if(auxiliary[j]==1)
{
continue;
}
if(arr[i]-arr[j] == k)
{
printf("{ %d ,%d } ",arr[i],arr[j]);
}
else if(arr[j]-arr[i] == k)
{
printf("{ %d ,%d } ",arr[j],arr[i]);
}
}
}
}
//print array elements
void print_array(int arr[],int size)
{
for(int i=0; i < size; i++)
{
printf(" %d ",arr[i] );
}
}
int main()
{
//Define collection of array elements
int arr[] = { 1, 4, 5, 2, 2, 2, 5, 5,4, 2 ,8, 4};
//Get the size of array
int size=(sizeof(arr)/sizeof(arr[0]));
print_array(arr,size);
difference(arr,size,3);
return 0;
}
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }#include<iostream>
using namespace std;
/*
C++ Program
Print all distinct pairs with given difference in array
*/
class MyArray {
public:
void difference(int arr[], int size, int k) {
if (size <= 0) {
return;
}
int auxiliary[size];
//Find Duplicates
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
if (arr[i] == arr[j]) {
//When get repeated element
auxiliary[j] = 1;
}
}
}
cout << "\nPairs of difference " << k << "\n";
for (int i = 0; i < size; ++i) {
if (auxiliary[i] == 1) {
continue;
}
for (int j = i + 1; j < size; ++j) {
if (auxiliary[j] == 1) {
continue;
}
if (arr[i] - arr[j] == k) {
cout << "{ " << arr[i] << " ," << arr[j] << " } ";
} else
if (arr[j] - arr[i] == k) {
cout << "{ " << arr[j] << " ," << arr[i] << " } ";
}
}
}
}
//print array elements
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i] << " ";
}
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
1,
4,
5,
2,
2,
2,
5,
5,
4,
2,
8,
4
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.print_array(arr, size);
obj.difference(arr, size, 3);
return 0;
}
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }/*
Java Program
Print all distinct pairs with given difference in array
*/
public class MyArray {
public void difference(int []arr,int size,int k)
{
if(size<=0)
{
return;
}
//For check duplicates nodes
int []auxiliary= new int[size];
//Find Duplicates
for (int i = 0; i < size; ++i)
{
for (int j = i+1; j < size; ++j)
{
if(arr[i]==arr[j])
{
//When get repeated element
auxiliary[j]=1;
}
}
}
System.out.print("\nPairs of difference "+k+"\n");
for (int i = 0; i < size; ++i)
{
if(auxiliary[i]==1)
{
continue;
}
for (int j = i+1; j < size; ++j)
{
if(auxiliary[j]==1)
{
continue;
}
if(arr[i]-arr[j] == k)
{
System.out.print("{ "+arr[i]+" ,"+arr[j]+" } ");
}
else if(arr[j]-arr[i] == k)
{
System.out.print("{ "+arr[j]+" ,"+arr[i]+" } ");
}
}
}
}
//print array elements
void print_array(int []arr,int size)
{
for(int i=0; i < size; i++)
{
System.out.print(" "+arr[i]+" " );
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define collection of array elements
int []arr = { 1, 4, 5, 2, 2, 2, 5, 5,4, 2 ,8, 4};
//Get the size of array
int size = arr.length;
obj.print_array(arr,size);
obj.difference(arr,size,3);
}
}
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }/*
C# Program
Print all distinct pairs with given difference in array
*/
using System;
public class MyArray {
public void difference(int[] arr, int size, int k) {
if (size <= 0) {
return;
}
//For check duplicates nodes
int[] auxiliary = new int[size];
//Find Duplicates
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
if (arr[i] == arr[j]) {
//When get repeated element
auxiliary[j] = 1;
}
}
}
Console.Write("\nPairs of difference " + k + "\n");
for (int i = 0; i < size; ++i) {
if (auxiliary[i] == 1) {
continue;;
}
for (int j = i + 1; j < size; ++j) {
if (auxiliary[j] == 1) {
continue;;
}
if (arr[i] - arr[j] == k) {
Console.Write("{ " + arr[i] + " ," + arr[j] + " } ");
} else
if (arr[j] - arr[i] == k) {
Console.Write("{ " + arr[j] + " ," + arr[i] + " } ");
}
}
}
}
//print array elements
void print_array(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i] + " ");
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Define collection of array elements
int[] arr = {
1,
4,
5,
2,
2,
2,
5,
5,
4,
2,
8,
4
};
//Get the size of array
int size = arr.Length;
obj.print_array(arr, size);
obj.difference(arr, size, 3);
}
}
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }<?php
/*
Php Program
Print all distinct pairs with given difference in array
*/
class MyArray {
public function difference($arr, $size, $k) {
if ($size <= 0) {
return;
}
//For check duplicates nodes
$auxiliary = array_fill(0, $size, 0);
//Find Duplicates
for ($i = 0; $i < $size; ++$i) {
for ($j = $i + 1; $j < $size; ++$j) {
if ($arr[$i] == $arr[$j]) {
//When get repeated element
$auxiliary[$j] = 1;
}
}
}
echo("\nPairs of difference ". $k ."\n");
for ($i = 0; $i < $size; ++$i) {
if ($auxiliary[$i] == 1) {
continue;
}
for ($j = $i + 1; $j < $size; ++$j) {
if ($auxiliary[$j] == 1) {
continue;
}
if ($arr[$i] - $arr[$j] == $k) {
echo("{ ". $arr[$i] ." ,". $arr[$j] ." } ");
} else
if ($arr[$j] - $arr[$i] == $k) {
echo("{ ". $arr[$j] ." ,". $arr[$i] ." } ");
}
}
}
}
//print array elements
function print_array($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i] ." ");
}
}
}
function main() {
$obj = new MyArray();
//Define collection of array elements
$arr = array(1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4);
//Get the size of array
$size = count($arr);
$obj->print_array($arr, $size);
$obj->difference($arr, $size, 3);
}
main();
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }/*
Node Js Program
Print all distinct pairs with given difference in array
*/
class MyArray {
difference(arr, size, k) {
if (size <= 0) {
return;
}
//For check duplicates nodes
var auxiliary = Array(size).fill(0);
//Find Duplicates
for (var i = 0; i < size; ++i) {
for (var j = i + 1; j < size; ++j) {
if (arr[i] == arr[j]) {
//When get repeated element
auxiliary[j] = 1;
}
}
}
process.stdout.write("\nPairs of difference " + k + "\n");
for (var i = 0; i < size; ++i) {
if (auxiliary[i] == 1) {
continue;
}
for (var j = i + 1; j < size; ++j) {
if (auxiliary[j] == 1) {
continue;
}
if (arr[i] - arr[j] == k) {
process.stdout.write("{ " + arr[i] + " ," + arr[j] + " } ");
} else
if (arr[j] - arr[i] == k) {
process.stdout.write("{ " + arr[j] + " ," + arr[i] + " } ");
}
}
}
}
//print array elements
print_array(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i] + " ");
}
}
}
function main(args) {
var obj = new MyArray();
//Define collection of array elements
var arr = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4];
//Get the size of array
var size = arr.length;
obj.print_array(arr, size);
obj.difference(arr, size, 3);
}
main();
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }# Python 3 Program
# Print all distinct pairs with given difference in array
class MyArray :
def difference(self, arr, size, k) :
if (size <= 0) :
return
# For check duplicates nodes
auxiliary = [0] * size
# Find Duplicates
i = 0
while (i < size) :
j = i + 1
while (j < size) :
if (arr[i] == arr[j]) :
# When get repeated element
auxiliary[j] = 1
j += 1
i += 1
print("\nPairs of difference ", k ,"\n", end = "")
i = 0
while (i < size) :
if (auxiliary[i] == 1) :
i += 1
continue
j = i + 1
while (j < size) :
if (auxiliary[j] == 1) :
j += 1
continue
if (arr[i] - arr[j] == k) :
print("{ ", arr[i] ," ,", arr[j] ,"}", end = "")
elif (arr[j] - arr[i] == k) :
print("{ ", arr[j] ," ,", arr[i] ,"}", end = "")
j += 1
i += 1
# print array elements
def print_array(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i] ," ", end = "")
i += 1
def main() :
obj = MyArray()
# Define collection of array elements
arr = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4]
# Get the size of array
size = len(arr)
obj.print_array(arr, size)
obj.difference(arr, size, 3)
if __name__ == "__main__":
main()
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 , 1 }{ 5 , 2 }{ 8 , 5 }# Ruby Program
# Print all distinct pairs with given difference in array
class MyArray
def difference(arr, size, k)
if (size <= 0)
return
end
# For check duplicates nodes
auxiliary = Array.new(size, 0)
# Find Duplicates
i = 0
while (i < size)
j = i + 1
while (j < size)
if (arr[i] == arr[j])
# When get repeated element
auxiliary[j] = 1
end
j += 1
end
i += 1
end
print("\nPairs of difference ", k ,"\n")
i = 0
while (i < size)
if (auxiliary[i] == 1)
i += 1
next
end
j = i + 1
while (j < size)
if (auxiliary[j] == 1)
j += 1
next
end
if (arr[i] - arr[j] == k)
print(" { ", arr[i] ," ,", arr[j] ," } ")
elsif (arr[j] - arr[i] == k)
print(" { ", arr[j] ," ,", arr[i] ," } ")
end
j += 1
end
i += 1
end
end
# print array elements
def print_array(arr, size)
i = 0
while (i < size)
print(" ", arr[i] ," ")
i += 1
end
end
end
def main()
obj = MyArray.new()
# Define collection of array elements
arr = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4]
# Get the size of array
size = arr.length
obj.print_array(arr, size)
obj.difference(arr, size, 3)
end
main()
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 } /*
Scala Program
Print all distinct pairs with given difference in array
*/
class MyArray {
def difference(arr: Array[Int], size: Int, k: Int): Unit = {
if (size <= 0) {
return;
}
//For check duplicates nodes
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
//Find Duplicates
var i: Int = 0;
var j: Int = 0;
while (i < size) {
j = i + 1;
while (j < size) {
if (arr(i) == arr(j)) {
//When get repeated element
auxiliary(j) = 1;
}
j += 1;
}
i += 1;
}
print("\nPairs of difference " + k + "\n");
i = 0;
while (i < size) {
if (auxiliary(i) != 1) {
j = i + 1;
while (j < size) {
if (auxiliary(j) != 1) {
if (arr(i) - arr(j) == k) {
print("{ " + arr(i) + " ," + arr(j) + " } ");
} else
if (arr(j) - arr(i) == k) {
print("{ " + arr(j) + " ," + arr(i) + " } ");
}
}
j += 1;
}
}
i += 1;
}
}
//print array elements
def print_array(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i) + " ");
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
//Define collection of array elements
val arr: Array[Int] = Array(1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4);
//Get the size of array
val size: Int = arr.length;
obj.print_array(arr, size);
obj.difference(arr, size, 3);
}
}
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 ,1 } { 5 ,2 } { 8 ,5 }/*
Swift Program
Print all distinct pairs with given difference in array
*/
class MyArray {
func difference(_ arr: [Int], _ size: Int, _ k: Int) {
if (size <= 0) {
return;
}
//For check duplicates nodes
var auxiliary: [Int] = Array(repeating: 0, count: size);
//Find Duplicates
var i: Int = 0;
var j: Int = 0;
while (i < size) {
j = i + 1;
while (j < size) {
if (arr[i] == arr[j]) {
//When get repeated element
auxiliary[j] = 1;
}
j += 1;
}
i += 1;
}
print("\nPairs of difference ", k ,"\n", terminator: "");
i = 0;
while (i < size) {
if (auxiliary[i] == 1) {
i += 1;
continue;
}
j = i + 1;
while (j < size) {
if (auxiliary[j] == 1) {
j += 1;
continue;
}
if (arr[i] - arr[j] == k) {
print("{ ", arr[i] ," ,", arr[j] ," } ", terminator: "");
} else
if (arr[j] - arr[i] == k) {
print("{ ", arr[j] ," ,", arr[i] ," } ", terminator: "");
}
j += 1;
}
i += 1;
}
}
//print array elements
func print_array(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i] ," ", terminator: "");
i += 1;
}
}
}
func main() {
let obj: MyArray = MyArray();
//Define collection of array elements
let arr: [Int] = [1, 4, 5, 2, 2, 2, 5, 5, 4, 2, 8, 4];
//Get the size of array
let size: Int = arr.count;
obj.print_array(arr, size);
obj.difference(arr, size, 3);
}
main();
Output
1 4 5 2 2 2 5 5 4 2 8 4
Pairs of difference 3
{ 4 , 1 } { 5 , 2 } { 8 , 5 }Time Complexity
The algorithm includes nested loops, both iterating through the array. In the worst case, these nested loops give a time complexity of O(n^2), where 'n' is the size of the array. The auxiliary array construction takes O(n), and the final time complexity of the solution remains O(n^2).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment