Posted on by Kalkicode
Code Array

Find pairs with given difference in array

The problem of finding pairs with a given difference in an array involves identifying all pairs of elements in the array whose absolute difference matches a specific target difference. This problem has various real-world applications, such as financial trading strategies, data analysis, and optimization algorithms. In this article, we will delve into the problem's details, explore an approach to solving it, provide a step-by-step algorithm, and explain its time complexity.

Problem Statement

Given an array of integers and a target difference 'K,' the task is to find and display all pairs of elements in the array such that the absolute difference between the pair's elements equals 'K.'

Example

Let's consider the array [4, 2, 7, 10, 2, 19, 1] and a target difference of 3. The pairs with an absolute difference of 3 are (7, 4), (4, 1), and (10, 7).

Idea to Solve the Problem

To solve this problem, we need to iterate through the array and for each element, check if there exists another element whose absolute difference with the current element equals the target difference. If such a pair is found, it should be displayed.

Pseudocode

``````find_difference_pairs(arr, size, difference):
status = 0
for i in range(size):
for j in range(i+1, size):
if abs(arr[i] - arr[j]) == difference:
print("Pair [ ({}) - ({}) ]".format(arr[i], arr[j]))
status = 1
if status == 0:
print("None")``````

Algorithm Explanation

1. Initialize a variable `status` to keep track of whether any pairs are found.
2. Iterate through the array using the outer loop with index `i`.
3. For each `i`, iterate through the remaining elements using the inner loop with index `j` starting from `i+1`.
4. Check if the absolute difference between `arr[i]` and `arr[j]` is equal to the target `difference`.
• If true, print the pair and update `status` to 1.
5. After both loops complete, if `status` remains 0, print "None" to indicate no such pairs were found.
``````// C Program
// Find pair with given difference
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Find all pairs of given difference in array
void find_difference_pairs(int arr[], int size, int difference)
{
int status = 0;
//Display array elements
printf("\n Array : ");
display(arr, size);
printf(" Difference : %d \n", difference);
//Outer loop
for (int i = 0; i < size; ++i)
{
//Inner loop
for (int j = i + 1; j < size; ++j)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
printf(" Pair [ (%d) - (%d) ] \n", arr[i], arr[j]);
status = 1;
}
//Check whether location j and i elements difference is equal to given difference
else if (arr[j] - arr[i] == difference)
{
printf(" Pair [ (%d) - (%d) ] \n", arr[j], arr[i]);
status = 1;
}
}
}
if (status == 0)
{
printf("\n None ");
}
}
int main()
{
int arr1[] = {
8 , 3 , 1 , 6 , 4
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
find_difference_pairs(arr1, size, 2);
int arr2[] = {
4 , 2 , 7 , 10 , 2 , 19 , 1
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
find_difference_pairs(arr2, size, 3);
return 0;
}``````

Output

`````` Array : 8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array : 4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````// Java Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Find pairs of given difference in array
public void find_difference_pairs(int[] arr, int size, int difference)
{
int status = 0;
//Display array elements
System.out.print("\n Array : ");
display(arr, size);
System.out.print(" Difference : " + difference + " \n");
//Outer loop
for (int i = 0; i < size; ++i)
{
//Inner loop
for (int j = i + 1; j < size; ++j)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
System.out.print(" Pair [ (" + arr[i] + ") - (" + arr[j] + ") ] \n");
status = 1;
}
else if (arr[j] - arr[i] == difference)
{
//When location j and i elements difference is equal to given difference
System.out.print(" Pair [ (" + arr[j] + ") - (" + arr[i] + ") ] \n");
status = 1;
}
}
}
if (status == 0)
{
System.out.print("\n None ");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
8,
3,
1,
6,
4
};
//Get the size of array
int size = arr1.length;
obj.find_difference_pairs(arr1, size, 2);
int[] arr2 = {
4,
2,
7,
10,
2,
19,
1
};
//Get the size of array
size = arr2.length;
obj.find_difference_pairs(arr2, size, 3);
}
}``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find all pairs of given difference in array
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Find pairs of given difference in array
void find_difference_pairs(int arr[], int size, int difference)
{
int status = 0;
//Display array elements
cout << "\n Array : ";
this->display(arr, size);
cout << " Difference : " << difference << " \n";
//Outer loop
for (int i = 0; i < size; ++i)
{
//Inner loop
for (int j = i + 1; j < size; ++j)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
cout << " Pair [ (" << arr[i] << ") - (" << arr[j] << ") ] \n";
status = 1;
}
else if (arr[j] - arr[i] == difference)
{
//When location j and i elements difference is equal to given difference
cout << " Pair [ (" << arr[j] << ") - (" << arr[i] << ") ] \n";
status = 1;
}
}
}
if (status == 0)
{
cout << "\n None ";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
8 , 3 , 1 , 6 , 4
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.find_difference_pairs(arr1, size, 2);
int arr2[] = {
4 , 2 , 7 , 10 , 2 , 19 , 1
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
obj.find_difference_pairs(arr2, size, 3);
return 0;
}``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````//Include namespace system
using System;
// C# Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Find pairs of given difference in array
public void find_difference_pairs(int[] arr, int size, int difference)
{
int status = 0;
//Display array elements
Console.Write("\n Array : ");
display(arr, size);
Console.Write(" Difference : " + difference + " \n");
//Outer loop
for (int i = 0; i < size; ++i)
{
//Inner loop
for (int j = i + 1; j < size; ++j)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
Console.Write(" Pair [ (" + arr[i] + ") - (" + arr[j] + ") ] \n");
status = 1;
}
else if (arr[j] - arr[i] == difference)
{
//When location j and i elements difference is equal to given difference
Console.Write(" Pair [ (" + arr[j] + ") - (" + arr[i] + ") ] \n");
status = 1;
}
}
}
if (status == 0)
{
Console.Write("\n None ");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
8 , 3 , 1 , 6 , 4
};
//Get the size of array
int size = arr1.Length;
obj.find_difference_pairs(arr1, size, 2);
int[] arr2 = {
4 , 2 , 7 , 10 , 2 , 19 , 1
};
//Get the size of array
size = arr2.Length;
obj.find_difference_pairs(arr2, size, 3);
}
}``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````<?php
// Php Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
public	function display( \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
//Find pairs of given difference in array
public	function find_difference_pairs( \$arr, \$size, \$difference)
{
\$status = 0;
echo "\n Array : ";
\$this->display(\$arr, \$size);
echo " Difference : ". \$difference ." \n";
//Outer loop
for (\$i = 0; \$i < \$size; ++\$i)
{
//Inner loop
for (\$j = \$i + 1; \$j < \$size; ++\$j)
{
//Check whether location i and j elements difference is equal to given difference
if (\$arr[\$i] - \$arr[\$j] == \$difference)
{
echo " Pair [ (". \$arr[\$i] .") - (". \$arr[\$j] .") ] \n";
\$status = 1;
}
else if (\$arr[\$j] - \$arr[\$i] == \$difference)
{
echo " Pair [ (". \$arr[\$j] .") - (". \$arr[\$i] .") ] \n";
\$status = 1;
}
}
}
if (\$status == 0)
{
echo "\n None ";
}
}
}

function main()
{
\$obj = new MyArray();
\$arr1 = array(8, 3, 1, 6, 4);
//Get the size of array
\$size = count(\$arr1);
\$obj->find_difference_pairs(\$arr1, \$size, 2);
\$arr2 = array(4, 2, 7, 10, 2, 19, 1);
//Get the size of array
\$size = count(\$arr2);
\$obj->find_difference_pairs(\$arr2, \$size, 3);
}
main();``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````// Node Js Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Find pairs of given difference in array
find_difference_pairs(arr, size, difference)
{
var status = 0;
process.stdout.write("\n Array : ");
this.display(arr, size);
process.stdout.write(" Difference : " + difference + " \n");
//Outer loop
for (var i = 0; i < size; ++i)
{
//Inner loop
for (var j = i + 1; j < size; ++j)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
process.stdout.write(" Pair [ (" + arr[i] + ") - (" + arr[j] + ") ] \n");
status = 1;
}
else if (arr[j] - arr[i] == difference)
{
process.stdout.write(" Pair [ (" + arr[j] + ") - (" + arr[i] + ") ] \n");
status = 1;
}
}
}
if (status == 0)
{
process.stdout.write("\n None ");
}
}
}

function main()
{
var obj = new MyArray();
var arr1 = [8, 3, 1, 6, 4];
//Get the size of array
var size = arr1.length;
obj.find_difference_pairs(arr1, size, 2);
var arr2 = [4, 2, 7, 10, 2, 19, 1];
//Get the size of array
size = arr2.length;
obj.find_difference_pairs(arr2, size, 3);
}
main();``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````#  Python 3 Program
#  Find all pairs of given difference in array
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

# Find pairs of given difference in array
def find_difference_pairs(self, arr, size, difference) :
status = 0
print("\n Array : ", end = "")
self.display(arr, size)
print(" Difference : ", difference ," \n", end = "")
# Outer loop
i = 0
while (i < size) :
# Inner loop
j = i + 1
while (j < size) :
# Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference) :
print(" Pair [ (", arr[i] ,") - (", arr[j] ,") ] \n", end = "")
status = 1

elif(arr[j] - arr[i] == difference) :
print(" Pair [ (", arr[j] ,") - (", arr[i] ,") ] \n", end = "")
status = 1

j += 1

i += 1

if (status == 0) :
print("\n None ", end = "")

def main() :
obj = MyArray()
arr1 = [8, 3, 1, 6, 4]
# Get the size of array
size = len(arr1)
obj.find_difference_pairs(arr1, size, 2)
arr2 = [4, 2, 7, 10, 2, 19, 1]
# Get the size of array
size = len(arr2)
obj.find_difference_pairs(arr2, size, 3)

if __name__ == "__main__": main()``````

Output

`````` Array :   8  3  1  6  4
Difference :  2
Pair [ ( 8 ) - ( 6 ) ]
Pair [ ( 3 ) - ( 1 ) ]
Pair [ ( 6 ) - ( 4 ) ]

Array :   4  2  7  10  2  19  1
Difference :  3
Pair [ ( 7 ) - ( 4 ) ]
Pair [ ( 4 ) - ( 1 ) ]
Pair [ ( 10 ) - ( 7 ) ]``````
``````#  Ruby Program
#  Find all pairs of given difference in array
class MyArray

# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
print("\n")
end
# Find pairs of given difference in array
def find_difference_pairs(arr, size, difference)

status = 0
# Display array elements
print("\n Array : ")
self.display(arr, size)
print(" Difference : ", difference ," \n")
# Outer loop
i = 0
while (i < size)

# Inner loop
j = i + 1
while (j < size)

# Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)

print(" Pair [ (", arr[i] ,") - (", arr[j] ,") ] \n")
status = 1
elsif(arr[j] - arr[i] == difference)

# When location j and i elements difference is equal to given difference
print(" Pair [ (", arr[j] ,") - (", arr[i] ,") ] \n")
status = 1
end
j += 1
end
i += 1
end
if (status == 0)

print("\n None ")
end
end
end
def main()

obj = MyArray.new()
arr1 = [8, 3, 1, 6, 4]
# Get the size of array
size = arr1.length
obj.find_difference_pairs(arr1, size, 2)
arr2 = [4, 2, 7, 10, 2, 19, 1]
# Get the size of array
size = arr2.length
obj.find_difference_pairs(arr2, size, 3)
end
main()``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]
``````
``````// Scala Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Find pairs of given difference in array
def find_difference_pairs(arr: Array[Int], size: Int, difference: Int): Unit = {
var status: Int = 0;
//Display array elements
print("\n Array : ");
display(arr, size);
print(" Difference : " + difference + " \n");
//Outer loop
var i: Int = 0;
while (i < size)
{
//Inner loop
var j: Int = i + 1;
while (j < size)
{
//Check whether location i and j elements difference is equal to given difference
if (arr(i) - arr(j) == difference)
{
print(" Pair [ (" + arr(i) + ") - (" + arr(j) + ") ] \n");
status = 1;
}
else if (arr(j) - arr(i) == difference)
{
//When location j and i elements difference is equal to given difference
print(" Pair [ (" + arr(j) + ") - (" + arr(i) + ") ] \n");
status = 1;
}
j += 1;
}
i += 1;
}
if (status == 0)
{
print("\n None ");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr1: Array[Int] = Array(8, 3, 1, 6, 4);
//Get the size of array
var size: Int = arr1.length;
obj.find_difference_pairs(arr1, size, 2);
var arr2: Array[Int] = Array(4, 2, 7, 10, 2, 19, 1);
//Get the size of array
size = arr2.length;
obj.find_difference_pairs(arr2, size, 3);
}
}``````

Output

`````` Array :  8 3 1 6 4
Difference : 2
Pair [ (8) - (6) ]
Pair [ (3) - (1) ]
Pair [ (6) - (4) ]

Array :  4 2 7 10 2 19 1
Difference : 3
Pair [ (7) - (4) ]
Pair [ (4) - (1) ]
Pair [ (10) - (7) ]``````
``````// Swift Program
// Find all pairs of given difference in array
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find pairs of given difference in array
func find_difference_pairs(_ arr: [Int], _ size: Int, _ difference: Int)
{
var status: Int = 0;
print("\n Array : ", terminator: "");
self.display(arr, size);
print(" Difference : ", difference ," \n", terminator: "");
//Outer loop
var i: Int = 0;
while (i < size)
{
//Inner loop
var j: Int = i + 1;
while (j < size)
{
//Check whether location i and j elements difference is equal to given difference
if (arr[i] - arr[j] == difference)
{
print(" Pair [ (", arr[i] ,") - (", arr[j] ,") ] \n", terminator: "");
status = 1;
}
else if (arr[j] - arr[i] == difference)
{
print(" Pair [ (", arr[j] ,") - (", arr[i] ,") ] \n", terminator: "");
status = 1;
}
j += 1;
}
i += 1;
}
if (status == 0)
{
print("\n None ", terminator: "");
}
}
}
func main()
{
let obj: MyArray = MyArray();
let arr1: [Int] = [8, 3, 1, 6, 4];
//Get the size of array
var size: Int = arr1.count;
obj.find_difference_pairs(arr1, size, 2);
let arr2: [Int] = [4, 2, 7, 10, 2, 19, 1];
//Get the size of array
size = arr2.count;
obj.find_difference_pairs(arr2, size, 3);
}
main();``````

Output

`````` Array :   8  3  1  6  4
Difference :  2
Pair [ ( 8 ) - ( 6 ) ]
Pair [ ( 3 ) - ( 1 ) ]
Pair [ ( 6 ) - ( 4 ) ]

Array :   4  2  7  10  2  19  1
Difference :  3
Pair [ ( 7 ) - ( 4 ) ]
Pair [ ( 4 ) - ( 1 ) ]
Pair [ ( 10 ) - ( 7 ) ]``````

Time Complexity Analysis

The algorithm involves nested loops. The outer loop runs `size` times, and the inner loop runs a maximum of `size-1` times for each outer iteration. Therefore, the overall time complexity is O(n^2), where `n` is the size of the array. This quadratic time complexity indicates that the algorithm's efficiency decreases as the array size increases.

Comment

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.

Categories
Relative Post