Skip to main content

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

  1. 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).
  2. Iterate through the original array, marking the indices of duplicate elements in the auxiliary array.
  3. 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

  1. Create a function difference(arr[], size, k):
    • Initialize an auxiliary array auxiliary of size size with 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.

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





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