CareerCup

could be done in On

static void sumExists(int a[],int sum){
		Hashtable ht=new Hashtable();
		int tmp=0;
		int num1=0,num2=0;
		boolean exist=false;
		
		for (int i = 0; i < a.length; i++) {
			ht.put(i, i);
		}
		
		for (int i = 0; i < a.length; i++) {
			num1=a[i];
			tmp=sum-num1;
			if(ht.get(tmp)!=null){
				exist=true;
				num2=tmp;
				break;
			}
		}
		
		if(exist){
			System.out.println(num1+ "+"+num2+ " = "+sum);
		}
		else
			System.out.println("doest exist");
	}

sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

This greedy algorithm is quite good.

Hash table

O(n)

No hash table
O(nlogn)

How?? Can you please explain.

I love it when people answer specific questions with data structures. Clearly shows they don't know what they are talking about. I have 7 solutions off the top of my head.

1.) Red black tree
2.) AVL tree
3.) Fibonnaci heap
4.) DAG
5.) DFA
6.) Stack
7.) Linear programming

1) Find the max, using a sort. nlog(n)
2) Populate a bit vector A[] with 1 for each integer in the array, 1 for those not in the array.
3) loop through the integer array, for each int i, if A[n-i]== 1. i and n-i are the two integers that add up to N.

There is no need to search in the 3rd step.

find min and max in O(n). then define a hash table with hashing function h(num)=num%d, where d=(max-min)/n.
now, for each element in an array search if the hash table contain a value (sum-num[i]) [i.e. search at the index h(sum-num[i])], if yes the present index and the number stored in hash table is the pair. If not, insert into hash table num[i].
Using this function, if we can assume that the numbers are uniformaly distributed, we can say that each bin will have one number on an avg. so the searching will be done in O(1). therefore total complexity is O(n).

Solution:
1. for each element in array add it to hashtable (HashSet in Java)
2. for each element in array, calculate sum-element, now lookup this value in the table. If it exists you're done

---------
sort the array (nlogn)
i=0, j=n-1 (j is set to last element of the array)

then use following algo ( O(n))

while i<j
if( (arr[i] + arr[j]) > val)
j--;
else if( (arr[i] + arr[j]) < val)
i++;
else
print arr[i], arr[j]

This greedy algorithm is quite good.
-----------

This algo won't work. check it out.

void Find_Two_number(int a[],int size,int number)
{
	int max =  a[0];
	int x = -1,y = -1;
	for (int i = 0;i<size;i++)
	{
		if(a[i]>max)
		{
			max =  a[i];

		}

	}

bool *b =  new bool[max+1];

for (int i = 0;i<=max;i++)
{

b[i] = false;

}

for (int i = 0;i<size;i++)
{

b[a[i]] = true;

}




for (int i = 0;i<size/2;i++)
{

if(b[a[i]] == true)
{

	if(b[number- a[i]] == true)
	{
		cout<< "X= "<< a[i]<<"; Y = "<< number-a[i]<<endl;

	}


}

}


}

Tell me if above sol dont work

yes, it could be done in linear.. O(n).

public void PairsOfArraySumsUpToGivenInteger(int[] arr, int sum)
        {
            int i = 0, j = i + 1;

            while (i < arr.Length)
            {
                if (arr[i] + arr[j] == sum)
                {
                    Console.WriteLine(arr[i] + "," + arr[j]);
                    j++;
                }
                else
                    j++;

                if (j >= arr.Length)
                {
                    i++;
                    if (i < arr.Length - 1)
                        j = i + 1;
                    else
                        break;

                }

}

Hashing seems to be perfect method if we want to reduce time complexity. It does have a space complexity of O(n), but that's not a concern I guess.

The above algorithm can be solved using hashing, keep calculating the difference of the given number to each element in the array if the element is present in the array then, return true else insert the element into the hashset and when it is not true then, at the end of the operation return false.

Implemenatation:

#include<bits/stdc++.h>
using namespace std;
bool findsum(int arr[], int n, int x){
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        int diff = x - arr[i];
        if(s.find(diff) != s.end())
            return true;
        s.insert(arr[i]);
    }
    return false;
}
int main(){
    int t, n, x;
    cin>>t;
    while(t--){
        cin>>n>>x;
        int arr[n];
        for(int i = 0; i < n; i++)
            cin>>arr[i];
        if(findsum(arr, n, x) == 1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
	//cout<<"Keep learning Keep growing"<<endl;
	return 0;

}