Searching

Question

Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that |a-b| = k , k being a positive integer.

a) O(logn)

b) O(n)

c)O(nlogn)

d)O(n^2)

Which of the option is Correct And Why?

Comments

i believe answer is O(nlogn) . Question is taken from geekforgeeks mock test but progrma for it not given ,

I found this https://www.geeksforgeeks.org/count-pairs-difference-equal-k/ here time is not less than O(nlogn).

anyone write its code  for O(n) :)

---

what will be the solution if it ask to find more than one pairs whose difference is k???

Answer 1

look answer would be b

If array is sorted in ascending order you need to keep two pointer one on left and other on right side..now subtract these two number and check weather its equal to k or not if not than two possibilities come wether some in less than k or greater than k.

if sum is greater than k decrease right pointer and if sum less than k than increase left pointer...so max it will take O(n) time find weather such two no. exists or not.!

Comments

Do it for

2,3,10,12,15,20 and k= 7

---

yeah bro. for this example the algorithm explained wont work.  any other approach?

---

when right pointer value =3

left pointer value=2

difference will be 3-2=1 which is less than required hence we r incrementing left pointer and now l

left pointer value=right pointer(3==3) value

now difference will be zero which is 0<7

hence we will increment left pointer which is now 10

now left pointer value =10 and right pointer value =3

difference will get 10-3=7 algorithm runs fine .!!!!

Answer 2

It Takes O(N)

As an array is already sorted one.. Just use two pointers one at start(Bcz it was the least number) and increment other one until you get a-b=k...  You just need one linear search

Best case is O(1)

Worst Case is O(n)

Comments

Bro, it may leads to O(n^2). Because u explained it for only 1st pass. what if the the element in the second pass or even in the last pass like below.

eg) 5 6 4 9 2 7 10 8 and difference is 2

Check it

---

just go with linear search... take first element as "a" and later on just move "b"... It takes only a linear search right

---

As per above question it is sorted one... your eg is not sorted one kindly check it

Answer 3

Ans is O(n)

when we solve this problem by using hashing then it take O(n) time

when we solve by using binary search or any other method it takes at least O(nlogn) time and in worstcase it takes O(n2).

by using hashmap,

 Initialize count as 0.
 Insert all distinct elements of arr[] in a hash map.  While inserting, 
   ignore an element if already present in the hash map.
 Do following for each element arr[i].
   a) Look for arr[i] + k in the hash map, if found then increment count.
   b) Look for arr[i] - k in the hash map, if found then increment count.
   c) Remove arr[i] from hash table. 

Comments

It doesn't matter whether the array is sorted or not, we can do it in O(n) (linear time) time. Use hashing.

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    map<int,int>mp;      // for hashing ()
    for(int i=0;i<n;i++)
    cin >>arr[i];
    
    for(int i=0;i<n;i++)  // O(n)
    {
        if(mp[arr[i]-k] || mp[arr[i]+k])
        {
            cout<<"Present"<<endl;
            break;
        }
        mp[arr[i]]=1;
    }
    return 0;
}

Answer 4

Consider the sorted array

45  47  49  50 55  57  66

Now I have chosen k = 1. That means the only place where we are going to get a hit is the highlighted position.

Now calculate 49-1 = 48 and 49+1 =50  (ie. 49+k and 49 - k is calculated)

Now if we can find these values in the array that means the algorithm returns true value and for that particular entry (in this case 49) in the array. If we could not find these values then it returns false for that particular entry . As the array is sorted, we can employ a binary search which takes O(log n) to find these calculated values.

If we could apply the same procedure from A[0] to A[n-1], we get a working algorithm. As the binary search is applied as many times as the number of elements in the array the time complexity is O(n log n).

The algorithm i have used is given below.

If you find any discrepancy or contradicting examples, please comment.

for i = 0 to n-1
{
    x = A[i] +1;
    y = A[i] -1;
    if (binarysearch(x) == 1 || binarysearch(y) == 1)
        {
            return true;
            break;
        }
}
return false;