Find a pair with the given difference in C++

In this tutorial, we will learn to find a pair with the given difference in C++. Also, we have given an array and a number n and our task is to get the pair whose difference is the given number.

For Example:

• Given Array= {1,2, 4, 6, 15, 20, 80 }
• n=76
• Now, we will get 76 if subtract 80 from 4
• 80-4=76
• pair: (4,80)
• If n= 55,
• Then, pair is not found.

Approach:

Simple Method:

• Firstly, iterate through two loops.
• Now, the outer loop will pick the element which is smaller.
• And, the inner loop will pick the element which is equal to the sum of the element which is picked by outer loop plus n.
• Time complexity: O(n^2)

Moreover, we can use binary search to improve the time complexity of the code.

Efficient Method:

• Firstly, we will assume the array is sorted.
• Now, initialize i and j variables with 0 and 1 respectively.
• Iterate through a loop.
• And, now check the condition, if i is not equal to j and difference of arr[j] and arr[i] is equal to n, then return pair.
• If arr[j] – arr[i] is less than n, then increment j.
• else increment i.
• Time complexity: O(n)

In spite of this, we can also use the hashing technique to solve this problem.

You may also like:
Sort elements on the basis of frequency in a string in C++

 

Find a pair with the given difference in an array in C++

Implementation:

#include<iostream> 
#include <bits/stdc++.h> 
using namespace std; 

// we are assuming array is sorted 
bool getPair(int arr[], int mn, int d) 
{ 
  // Initialize index positions 
  int i = 0; 
  int j = 1; 

  // Searching pair
  while (i < mn && j < mn) 
  { 
    if (i != j && arr[j] - arr[i] == d) 
    { 
      cout << arr[i] << ", " << arr[j]; 
      return true; 
    } 
    else if (arr[j]-arr[i] < d) 
      j++; 
    else
      i++; 
  } 

  cout << "No pair found"; 
  return false; 
} 


int main() 
{ 
  int arr[] = {1,2,4,6,15,20,80}; 
  int mn = sizeof(arr)/sizeof(arr[0]); // size
  int d = 76; // number
  getPair(arr, mn, d); 
  return 0; 
} 

Output Explanation:

INPUT: { 1,2,4,6,15,20,80 }
                 d=76
OUTPUT: (4,80)