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)
Leave a Reply