fresh_coder
BAN USER
Comments (4)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Algo is right, a little bug while coding. doing a binary search on entire array will be a killer in case sum being searched is double of an element of the array.
e.g. array= 2,3,5,7. sum=6.
Comment hidden because of low score. Click to expand.
0
of 0 vote
An interesting case is if array contains duplicate numbers. Above code will report only one such pair.
e.g. Let the sorted array be 2,5,5,5,6,8,9 and we are searching for elements adding up to 10. This will report only one such pair.
Following Algorithm will help get rid of that issue:
1. Sort
2. For each a[i], Get j = BinarySearch for (x-a[i]) in array between indices i+1 & n-1
3. Print i,j
Comment hidden because of low score. Click to expand.
0
of 0 vote
@selvan: What is the input where you see it won't give you correct results?
@gopi: No thats not the assumption.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
ALGO
--------
Cover elements diagonally till diagonal element is less than the element being searched and there are more elements in diagonal. Post that if there are remaining rows or columns, cover all the elements there.
COMPLEXITY
-----------------
Max(m,n)
PSEUDOCODE
--------------------
- fresh_coder March 28, 2012