CREATE OWN LIBRARY
Difference of two elements
Back to ProgrammingDescription
You are given a sorted array and a value which is the difference of two elements in the array. Return the 2 elements if found else return not found. There is only one pair of elements in the array. Find in O(n) time.
Example:
0 | 2 | 6 | 8 | 9 |
Value = 7
O/P:
2 | 9 |
Difference of 2 and 9 is 7
Explanation:
Given a sorted array. If we find difference for every pair of elements and compare with the given value then time complexity becomes O(n2).
i.e.
.png)
We have to solve in O(n) time
0 | 2 | 6 | 8 | 9 |
Algorithm
Step 1: Initialize two values i and m with 0 and 1 respectively.
i = 0
m = 1
Step 2: Run a loop till m < size of the array
Step 3: Now check the absolute difference of arr[i] and arr[m]
if arr[i] – arr[m] == d /d = difference ,/we got the pair, return it
else if arr[i] – arr[m] < d /i.e. if the difference is small then increment m by 1 than the required i.e. make 1 index to the
right to increase the difference
else /i.e. the difference is greater than the require. So we have reduce the difference
increment i by 1
Step 4: Run step 2 to 3 until condition fails.
Step 5: Return not found if pair is not
.png)
Code
Time complexity: O(n)
Space complexity: O(1)
