CareerCup

This could be solved with Hash table.

1. Parse through the entire Array. If the value is less than the sum, lets say , a then Has this value in to the hash table.
2. Traverse the entire array again, for element b[i], Lookup hash[a-b[i]] if it does exist then b[i] and the a-b[i] exist in the array and make the pair.

Can some one give it with O(n) run time and constant space instead of hash table?

"If the value is less than the sum"... what if we're allowing negative numbers (which, since we haven't said otherwise, we probably are)?

Sorth array using quick sort. o(nlogn) complexity.
Now for each element a[i], find N-a[i] using binary search.O(log n)

I think you can get in O(nlog n) + o(logn) complexity.

This one is straight from Cormen's book. The problem looks more easy if we think of finding the N-a[i] value.

sp, u don't need an internal ref in order to get an interview.
my friend got 2 offers at the same time without an internal reference.

hi someone, thanks for taking the time. was just wondering if applying thru the site helps. any inputs on that. thanks

applyin thru site helps...i applied and i was contacted for an interview within few weeks...so go ahead

By using a hash table, you can do this in linear time. Is there a solution that run in linear time without using a lot of memory?

Can you elaborate your hash table method? how to use a hash table in this case?

You can split this into 2 cases:

1. N is Even
n1,n2 are odd
n1,n2 are even.

2. N is Odd
n1 even, n2 odd
n2 odd, n2 even.

This will remove certain unnecessary comparisons.

Using hash table, I think it is possible to do in O(n).

Array : a[]
Sum required : value

1. Take each element, a[i], from the array. Apply hash function, h(a[i]), to it.
1.1. Now apply same hash function to h(value - a[i]). If there exists a value in that place then these two numbers are victim. Here, we need to check that index this hash functions yield is not out of array bounds.

1.2. make an entry in hash table for a[i].

Continue above steps.

Using a data structure should be your last option as duplicate storage is sometimes unnecessary.

1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution

1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution

Doesn't Radix Sort assume fixed length of the input numbers, i.e. a constant no. of digits. There is no mention of that fact in the question.

Doesn't Radix Sort assume fixed length of the input numbers, i.e. a constant no. of digits. There is no mention of that fact in the question.

Think: Dynamic Programming!

This is a good case for the Subset Sum algorithm. Where the value at c[k, u] (k is the index of the value we are using and, u, is the actual weight - the sum) is the actual capacity. This can be done with the max of {(k-1, u-value[k]) + value[k], (k-1, u)}.

If you want to limit it to only 2 values from the array then all you have to do is find the minimum of the recurrence I gave above.. and instead of adding value[k] you add a 1. If c[k, u] gives you 2, then there are 2 values in the aray that add up to u.

Given C, find A and B such that A + B = C.
Answer: choose A to be any number and let B = C - A.

If we can assume that the array is sorted then,
you can have 2 variabled one for first index, other for last index(end).
if sum of values at those index is less than the value needed, increment end index
if the sum is greater than, increment front index
if they are equal, u have found the one needed.
If front equals or crosses over back then its not present in the array.

func(int total)
{
int a=0;
int b=0;

if(total != 0)
{
a = total/2;
b = total - a;
}
// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
}

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
func(int total)
{
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}
}

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
int total = rand(); // or whatever is passed
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total

int total = rand(); // or whatever is passed
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}

Kiran, Your algo assumes that the original input is sorted. This is a point which might be true. Khoa, the hash method is definitely good but yeah it requires extra memory but the only one i can think of in O(n).

how write the algorithem that prints the sum of the first n positeve integer??

The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}

The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=&arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}

For unsorted array this code should work:

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
for (int i=0;i<len-1;i++)
for (int j=i+1;j<len;j++)
{
if (arr[i]+arr[j]==sum)
{
*num1=arr[i];*num2=arr[j];return 0;//success
}
}

return -1; //Such numbers are not present in the array

}

good solution thax

n*(n+1)/2

Store the array in binary tree, instead of hash table. Here we will require less memory but time will be O(nlogn) and then searching for number will be O(logn) so overall all nlogn + logn

Can someone build the hash table for this problem??

Use inplace sort that will take O(nlogn) time. And have two pointers at:

startindex = 0 and lastindex = last

find the sum if this sum > resultsum
lastindex = lastindex - 1
else if sum < resultsum
startindex = startindex + 1
else // the numbers found.
print element at startindex and lastindex.

do this for until we find the elements.

This will be done in O(n) so, O(nlogn) is the max time with minimal memory.

Can someone explain the hash function please?
Pratik: How will you make sure that arr[i] and (sum - arr[i) will hash to the same location??

I dont think thats a good solution. It is taking O(n**2) time. sorting solutions looks fine to me. O(n/2) + O(n log n) = O(n log n)

#define sum 100
#define HASHSIZE 256
int hash[256];
int main()
{
int a[] = {30,70,40,60,50,50};
int index = 0;
for(index=0;index<HASHSIZE;index++)
hash[index]=0;
index =0;
while(index<sizeof(a)/4){
hash[a[index]]=1;
index++;
}
index = 0;
while(index <sizeof(a)/4){
if(hash[(sum-a[index])]==1)
printf("%d and %d\n",a[index],sum-a[index]);
index++;
}
return(0);
}

Time Complexity is O(n) using the above approach.

Assumption:
1) Unordered.
2) Unique

Just a simple logic, for simplicity not including checks like if element is < sum or not, or if number is -ve etc etc.

1.) Use a bit vector of length = (given_sum)
2.) Scan the array, for each element read, mark the corresponding bit in the bit vector, for example number 5 will set 5th bit to 1 in the bit vector.
3.) Scan the array again, for each element say i check if (sum-i)th bit in the bit vector is SET (or 1. If yes this is the pair. In this way you can find all the pairs.

We can avoid 2nd iteration through the array as well, while scanning the array for the first time, include the checks to find the other paired number as well (whether or not it is set to 1)

assume length of array is N;
foreach number in the array
check hash(sum - number),
if exist, return
else hash(number): slot = number % N; insert number to hash table

1) iterate through the array -- put each value into a hashtable (the key is input[i], the value is the number of times that value has occurred)
2) iterate through the array again -- int myValue = sum-input[i]
3) if myValue == input[i], then make sure myValue occurs in the array more than just once. if it does, then that's a pair
4) if myValue != input[i], then if myValue occurs in the array 1 or more times, then that is a pair.

Using sorting,

Time complexity : o(nlogn)

import java.io.*;
import java.util.*;
public class Sum2 
{
	// Global variables 
	static int len=0,sum=0;  
	private static int array[] =new int[len]; // initialization of array length as 0
	
	public static void main(String args[]) throws NumberFormatException, IOException
	{	
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter length of array");
		len =Integer.parseInt(br.readLine()); // take length of array from user  
		
		setArray(Arrays.copyOf(getArray(), getArray().length + len));  // reinitialize array to given length
		
		System.out.println("Enter elements:"); // takes input
		for(int i=0;i<len;i++)
			getArray()[i]=Integer.parseInt(br.readLine());
		
		System.out.println("Enter sum:");
		sum =Integer.parseInt(br.readLine());
		
		Sum2 s = new Sum2(); 
		Quicksort q = new Quicksort();
		
		q.sort(0,getArray().length-1); // perform sorting
		s.find2sum(); // to find pair in A[] with sum as x
	}
	
	/***************************************************************************
	    *  Method for finding pair in A[] with sum as x
	 ***************************************************************************/
	void  find2sum()
	{
		System.out.println("Output pairs:");
	    int lo = 0;
	    int hi = array.length-1; 
	    while (lo < hi)
	    {
	        if((array[lo] + array[hi]) == sum)
	        	System.out.println("Pair with given sum "+sum+" is (" + array[lo]+", "+array[hi]+")");
	        if((array[lo] + array[hi]) < sum)
	 	        lo++;
	 	     else 
	 	        hi--;
	         }	        	        	         
	}	
	
	/***************************************************************************
	    * functions to access array
	 ***************************************************************************/	
	public static int[] getArray() {
		return array;
	}
	
	public static void setArray(int array[]) {
		Sum2.array = array;
	}
}
/***************************************************************************
 *  QuickSort Algorithm
***************************************************************************/
class Quicksort 
{
	static Quicksort q1= new Quicksort();
	
	void sort(int low,int high) // Check whether an array is empty
	{		
		if(high<=low)
			return ;
		int j=partition(low,high);
		// recursive call to quickSort() method 
		sort(low,j-1);
		sort(j+1,high);
	}
	
	int partition(int low,int high)
	{
		int i=low;
		//System.out.println(s1.getArray()[low]);
		int j=high+1;
		int pivot=Sum2.getArray()[low]; 
		while(true)
		{
			while(Sum2.getArray()[++i]<pivot) // find item on low to swap
				if (i == high) break; // Boundary case
			
			while(Sum2.getArray()[--j]>pivot)  // find item on high to swap
				if (j == low) break;   // Boundary case
			// check if pointers cross
			if (i >= j) break;
				q1.exchange(i,j);
			
		}
		exchange(low, j);
		return j;
	}

	void exchange(int i,int j)
	{	
		int temp=Sum2.getArray()[i];
		Sum2.getArray()[i]=Sum2.getArray()[j];
		Sum2.getArray()[j]=temp;
	}

}

/***************************************************************************
OUTPUT: 

Enter length of array
8
Enter elements:
55
181
45
69
-81
3145
31
801
Enter sum:
100
Output pairs:
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
Pair with given sum 100 is (45, 55)
***************************************************************************/

using hashing,

Time complexity : o(n)

import java.io.*;
import java.util.*;

public class Sum2Hash 
{
	public static void main(String args[]) throws NumberFormatException, IOException
	{
		Sum2Hash s=new Sum2Hash();
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); 
		System.out.println("Enter array length");
		int len =Integer.parseInt(br.readLine());
		
		
		int array[]=new int[len];
		System.out.println("Enter Element");
		for(int i=0;i<array.length;i++)
			array[i]=Integer.parseInt(br.readLine());
	
		System.out.println("Enter sum:");
		int sum =Integer.parseInt(br.readLine());
		
		s.findpairs(array, sum);
	}

	void findpairs(int array[],int sum)
    {
		 Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
 
        for (int i=0; i<array.length; i++)
        {
        	if(pairs.containsKey(array[i]))
	            System.out.println("Pair with given sum "+sum+" is ("+array[i] +", "+ pairs.get(array[i])+")");
	        else
	            pairs.put(sum-array[i], array[i]);
        }
    }
}

/***************************************************************************
OUTPUT: 

Enter array length
8
Enter Element
55
181
45
69
-81
3145
31
801
Enter sum:
100
Pair with given sum 100 is (45, 55)
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
***************************************************************************/

1. sort the array
2. kep one pointer at smallest and one at largest,
3. Use binary search to bring the largest pointer to either the x-a[0] or if that is not there just smaller one.
3. now increase left if smaller or decrease right if bigger(perhaps here too we should use binary search to increase or decrease)

hmmm theres no o(n) best case. avg case for the hash table is o(n) and thats the best.

This is abt the amazon application. Is it necessary to have an internal ref to get an interview i.e., does applying thru the site help? thanks