CareerCup

as arrays are sorted use binary serach for finding ( X-array1[i]) in array2

May be there can't be any such solution, with less than O(n) worst case complexity.
Lets see...

suppose someone proposes an algo. which does this in sublinear time, that means
that algorithm will not look at every element, and it is theoretically possible to put those two elements at those positions which is not looked by that algorithm.
Hence looking at every element is necessary in worst case. So we need O(n) time.

But there is a catch, since the array is ordered, there may be a algorithm which does not literally looks at every element but takes advantage of this information about ordering of elements, And thus i think it may be possible to have such algorithm. Although I am not sure.

What I tried ,
take first element of the array, call it "x", now binary search for largest element less equal than (Sum - x). if the sum of those elements is Sum, then we have the answer.
Otherwise, Take second element of array. call it "y", now binary search (Sum - y) in the new limited range. But i guess the time complexity is not better than O(n).

Thanks.

void sumX(int *a,int n,int x)
{
int p1=0;//first elem
int p2=n;//last elem
while(p2>p1)
{
int sum=a[p1]+a[p2];
if(sum<x)p1++;
elseif(sum>x)p2--;
else
cout<<a[p1] <<" "<<a[p2];
}

there are no sub-linear solution, the search space is O(n2) (i.e. all pair sums of the array), and its proven that you can not do better than linear time. you can google selection in X+Y sorted arrays to see the general problem.

garimaa.blogspot.in/2012/04/program-6th-in-c.html

Hi All, I wrote this O(n) program in Java. I didn't find any solution that is less than this.

public class SortedArrayPairSum {
    public static void main(String [] args) {
        List<Integer> sortedArray = Lists.newArrayList(1, 5, 10, 12, 30, 60);
        int sumExpected = 42;
        int frontPointer = 0;
        int backPointer = sortedArray.size() - 1;
        while (frontPointer < backPointer) {
            int actualSum = sortedArray.get(frontPointer) + sortedArray.get(backPointer);
            if(actualSum < sumExpected) {
                frontPointer++;
            }
            else if(actualSum > sumExpected) {
                backPointer--;
            }
            else {
                System.out.println("Pair=(" + sortedArray.get(frontPointer)+","+ sortedArray.get(backPointer) + ") Sum=" + actualSum);
                break;
            }
        }
    }
}

class Node
{
public Node right;
public Node left;
public int value;
}
public class bettersum
{
public static int findhalf(int[] arg,int sum)
{
int i=0;
int j=arg.length;
int half=sum/2;
int output=0;
for(int k=i;k<j;k++)
if(arg[k]>half)
{
output=k-1;
break;
}
return output;
}
public static Node initializeBST(int[] arg,int middle)
{
int length=arg.length;
Node root=new Node();
Node temp=new Node();
temp=root;
for(int i=middle;i>=0;i--)
{

initialsingleleft(temp,arg[i]);
temp=temp.left;
}
root.right=new Node();
temp=root.right;
for(int i=middle+1;i<length;i++)
{
initialsingleright(temp,arg[i]);
temp=temp.right;
}
return root;
}

public static void findsum(Node root,int sum,int middle,int length)
{
Node temp= root.left;
Node temp1=root;
for(int i=middle;i<=length;i++)
{
for(int j=middle-1;j>=0;j--)
{
if(temp.value+temp1.value>sum)
{
temp=temp.left;
}
else if(temp.value+temp1.value==sum)
{
System.out.println(" "+temp.value+" "+ temp1.value);
break;
}
else
{
break;
}
}
temp1=temp1.right;
temp=root.left;
}

}
public static void initialsingleright(Node node, int value)
{
node.value=value;
node.right=new Node();
}
public static void initialsingleleft(Node node,int value)
{
node.value=value;
node.left=new Node();
}
public static void main(String args[])
{
int [] a ={1,2,3,4,5,6,7,8};
int sum =8;
int middle=findhalf(a,sum);
findsum(initializeBST(a,middle),sum,middle,a.length);
}
}

its all rubish u cant reduce from o(n).in worse ase it alwaz take o(n)

public static void FindTwoNumbers(int[] arr,int X)
        {
            Hashtable ht = new Hashtable();
           //let number's be x and y
           //X-arr[i]=y..is the same as X=arr[i]+y. 
           //So we can store the arr[i] in a hashtable and iterate through the array.
            for(int i=0;i<arr.Length;i++)
            {
               if(ht.ContainsKey(X-arr[i]))
               {
                   ht[X - arr[i]] = arr[i];
               }
               else
               {
                   ht.Add(arr[i],"");
               }
            }
            foreach (var obj in ht.Keys)
            {
                if(ht[obj].ToString().Length!=0)
                {
                    Console.WriteLine(obj.ToString() + "," + ht[obj].ToString());
                }
            }
        }

Explanation for above code
{1,2,3,4,5}....let us say we are searching for 7
so, 7-1=6, we lookup 6 in hastable, if it is found we have a pair otherwise we add 1
7-2=5, not there in hashtable, so add 2 to hash
7-3=4 hashtable now contains {1,2,3}
7-4=3, is 3 present in hastable,yay! we have a pair
7-5=2, is 2 present in hastable, yes wo we have another pair

Explanation for above code
{1,2,3,4,5}....let us say we are searching for 7
so, 7-1=6, we lookup 6 in hastable, if it is found we have a pair otherwise we add 1
7-2=5, not there in hashtable, so add 2 to hash
7-3=4 hashtable now contains {1,2,3}
7-4=3, is 3 present in hastable,yay! we have a pair
7-5=2, is 2 present in hastable, yes wo we have another pair