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.

New Comment