Find All Pairs With a Given Difference

Problem Statement

We have given an array of containing different elements or no repeated elements present in the array. Find all pairs with a given difference. If there is no any pair with given different then print “No pair with given different”.

Example

Input

10 20

90 70 20 80 50 25 35 15 100 150

Output

90 70

70 50

80 100

35 15  (Pair of elements with difference 20 will print)

Approach 1 for Find All Pairs With a Given Difference

Run two loops such that select one element from the array. Starting from the index 0, and look forward to the array to get a pair with a given difference.

a)    If we find the element then print them.
b)    Else print, not found.

Implementation

C++ Program for Find All Pairs With a Given Difference

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int flag=0;
  for(int i=0;i<n;i++)//select an element
  {
    for(int j=i+1;j<n;j++) // look forward in the array
        if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
        {
          cout<<a[i]<<"  "<<a[j]<<endl;
          flag=1;
        }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Java Program for Find All Pairs With a Given Difference

import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int flag=0;
        for(int i=0;i<n;i++)//select an element
        {
          for(int j=i+1;j<n;j++) // look forward in the array
              if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
              {
                System.out.println(a[i]+"  "+a[j]);
                flag=1;
              }
        }
        if(flag==0)
        System.out.println("No pair with given different");
    }
}

10 20
90 70 20 80 50 25 35 15 100 150

90  70
70  50
80  100
35  15

Complexity Analysis

Time Complexity

O(N*N) where N is the size of the given array. Simply check for each pair by running two for loops.

Space Complexity

O(1) because we don’t use any extra space here.

Approach 2 for Find All Pairs With a Given Difference

Step 1: First sort the given array. It takes O(NlogN).

Step 2: In the same way as the first algorithm, for every element starting from the first element, find the matching pair.

i)    Here we will use a binary search to find the element.
ii)    for element a and given difference n we search for a + n.

Example

Input

10 20

90 70 20 80 50 25 35 15 100 150

Find all pairs of elements with difference = 20

Apply Algorithm on the input array,

Steps by step working

1. Sort the array, Sorted array: 15 20 25 35 50 70 80 90 100 150
2. a = 15, difference (n)= 20 so, a + n = 35, binary_search(35, input array)= True. Print 15 35. Move forward
3. a = 20, difference (n)= 20 so, a + n = 40, binary_search(40, input array)= False. Move forward
4. a = 25, difference (n)= 20 so, a + n = 45, binary_search(45, input array)= False. Move forward
5. a = 35, difference (n)= 20 so, a + n = 55, binary_search(55, input array)= False. Move forward
6. a = 50, difference (n)= 20 so, a + n = 70, binary_search(70, input array)= True. Print 50 70. Move forward
7. a = 70, difference (n) = 20 so, a + n = 90, binary_search(90, input array) = True. Print 70 90. Move forward
8. a = 80, difference (n) = 20 so, a + n = 100, binary_search(100, input array) = True. Print 80 100. Move forward
9. a = 90, difference (n) = 20 so, a + n = 110, binary_search(110, input array) = False. Move forward
10. a = 100, difference (n) = 20 so, a + n = 120, binary_search(120, input array) = False. End of loop.

Implementation

C++ Program for Find All Pairs With a Given Difference

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sort(a,a+n);
  int flag=0;
  for(int i=0;i<n-1;i++)//select an element
  {
      int diff=a[i]+d;
      if(binary_search(a,a+n,diff))
      {
          cout<<a[i]<<" "<<diff<<endl;
          flag=1;
      }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Java Program for Find All Pairs With a Given Difference

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static int binary_search(int arr[], int l, int r, int x)
    {
        if (r >= l) 
        {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binary_search(arr, l, mid - 1, x);
            return binary_search(arr, mid + 1, r, x);
        }
        return -1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        int flag=0;
        for(int i=0;i<n-1;i++)//select an element
        {
            int diff=a[i]+d;
            if(binary_search(a,0,n-1,diff)!=-1)
            {
                System.out.println(a[i]+"  "+diff);
                flag=1;
            }
        }
        if(flag==0)
         System.out.println("No pair with given different");
    }
}

10 20
90 70 20 80 50 25 35 15 100 150

15 35
50 70
70 90
80 100