CareerCup

One solution that comes to my mind is we approach the solution through a greedy algorithm. We can read a constant number of positive integers from the file. This way it becomes memory efficient. Then apply the algorithm to find the pair of numbers which add up to x. This algo gives a sub optimal solution.

One solution that comes to my mind is we approach the solution through a greedy algorithm. We can read a constant number of positive integers from the file. This way it becomes memory efficient. Then apply the algorithm to find the pair of numbers which add up to x. This algo gives a sub optimal solution.

What if solution pair is (A,B), and A, B doesn't belong to same set of integers being read from file ?

Order the numbers with a merge sort (you can do this in batches), using the X as pivot. Now you know that only two numbers on the left can be added up to equals X. Then you can have i=0 and j=A[X] you will do j-- when X < A[i] + A[j] or you would i++ when X > A[i] + A[j]

scan the entire file and remove duplicates & numbers greater than X(100) , store the remaining numbers ( non-dups ) in a hash or linked list.. o(n)

sort them - o(nlogn )..

take first element (a) & start checking from last element(b) of the array or linked list to see if a+b = 100 ; continue this way till you reach the middle of array or linked list - 0(n)

If x is much smaller than N, space complexity would be O(x), time complexity would be O(N).

If N is much bigger than x: if a space complexity of O(N) is allowed, time complexity will be O(N).

If cannot have O(N) space, use an other file to store temp data in sorted order and a resulted file for results.
Space complexity = O(1), Time complexity O(NlogN)

There is a O(N) solution to this problem. Just maintain an array of size 100, A[100]. Now as you progress through the N numbers, if the current number x is smaller than 100 then try to find its complement (100-x)in A (see if A[100-x] == true). If it's there then you have the solution. If not then set A[x] = true.

There is a O(N) solution to this problem. Just maintain an array of size 100, A[100]. Now as you progress through the N numbers, if the current number x is smaller than 100 then try to find its complement (100-x)in A (see if A[100-x] == true). If it's there then you have the solution. If not then set A[x] = true

How about we try this out:
Lets say the numbers sum-up to SUM. Define a hashtable H.Then go through the numbers and for each number, n, check if n is in H and if its not, then you store SUM-n in H (i.e. you store the number needed to add n to give SUM). This allows you to scan for the needed number, and not those you have seen. Duplicates will be automatically eliminated as we wont store duplicates in has table. Algorithm will look something like this:

Hashtable H;
Number SUM;

for each number n in Numbers (assuming Numbers is an array)
if (H has n)
Then a pair is found (i.e. n and SUM-n)
else
Store SUM-n in H

I guess time complexity here will be O(N), not sure of space, i guess worst case of O(N) as well if all the numbers are different and no pair sums up to SUM

Number are positive I am using BitSet.

public class Amazon{
        BitSet aBitSet = new BitSet(Integer.MAX_VALUE);
        HashSet<Integer> aSet = new HashSet<Integer>();
        int sum=0; 
        public Amazon(String aFile,int sum) throws IOException{
             Scanner s = new Scanner(new File(aFile));
             this.sum = sum; 
             while(s.hasNextInt()){
                int x = s.nextInt();
                int y = sum - x;
                if(y>0 && aBitSet.get(y))
                   aSet.add(x);  
                else
                   aBitSet.set(x);
             }
        }
     public void printPair()
     {
        foreach(Integer i: aSet)
        {
           System.out.print(i);
           System.out.print(","); 
           System.out.print(sum-i);
           System.out.println();  
        }
       
     }
}

One solution which is coming to my mind is:
Divide the range of number into k number of subranges. We will maintain a datastructure with k number of buckets and populate the datastructure with numbers taken from the original array. time O(n), space O(n).

Now, sort the numbers in each range. Time: O(n*log(n/k)) on average, if numbers are well distributed.

The ranges are choosen in such a way the pairing of ranges are possible. For example, for x+y=100; If we have ranges 0-9, 10-19, 11-19 .., 50, ...,81-90, 91-100.

Here pairing will be like (0-9, 91-100), (10-19, 81-90), etc.

From each such pairs pickup one number at a time (by traversing one range top-down, and other bottom-up) and try to match sum with the given number (100 for example).

c++ code

func(int a[],int x)
{
map<int,int> table;
for(i=0;i<N;i++)
 {
if(p=table.count(a[i])==1)
    cout<<a[i]<<','<<x-a[i];}
else if (p==0)
   {
   table(x-a[i])=a[i];
   }
}

Hash table is the best solution to do in O(n) time and O(n) space.

Otherwise two pointer sum (one from the first and one on the last) after sorting the numbers would do in O(nlogn). In space comparison, hence no space complexity involved. Everything else ruled out!

Improving on mayank's solution and using only bitset. I don't see the need of hash if all we are doing is printing out.

public void PrintNumbers(String file,int sum) throws FileNotFoundException
	{
	 BitSet bs= new BitSet(sum);
	 //HashSet<Integer> hash = new HashSet<Integer>();
	 Scanner s= new Scanner(new File(file));
	  while(s.hasNextInt()){
		 int x=s.nextInt();
		 if(x<=sum){
			 if(bs.get(sum-x)==true){
			//if(hash.contains(sum-x)){
				System.out.println(x +"  "+(sum-x));
			    bs.set(sum-x, false);//To take care of duplicates
				}
			else 
				bs.set(x);
		 }
	  }
	 }