12,426 views
4 votes
4 votes

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?

7 Answers

5 votes
5 votes
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.!
2 votes
2 votes
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)
2 votes
2 votes

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. 
1 votes
1 votes

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;
Answer:

Related questions

0 votes
0 votes
1 answer
1
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
2 votes
2 votes
1 answer
3
4 votes
4 votes
1 answer
4