CareerCup

METHOD 1 :: Time - O(n^2), Space - O(1) [SIMPLE AND INEFFICIENT]
Name :: Brute Force Approach
Use 2 for loops.
For every element in 1st loop, try to find another element matching the sum in 2nd loop.

METHOD 2 :: Time - O(nlogn), Space - O(1) [TRICKY]
Name :: Sort and find approach
1. Sort the elements
2. Use 2 indexes from both ends and find the 2 elements matching the sum

METHOD 3 :: Time - O(n), Space - O(n) [EFFICIENT]
Name :: Hash and search approach
1. Insert all the elements into a hashmap
2. For every element x, check if there is (sum-x) element in the hashmap.

public static int[] find(int[] A, int z /*,int k if k is given */)
{
	int i,size;
	int B[z]; // it best to do max of (k,z)
	/* //if k is given
	if (z > 2k) return null;
	for(i =0; i < z; i++) B[i] = -1;
	*/
	for(i = 0; i < A.length /* note */; i++) // or use true and break when you reach the end of the array if you can't get size of   A
	{
		if (A[i] >= z) continues; // useless number
		if(B[z-A[i]] > 0) return {i, B[z-A[i]]};
		B[A[i]] = i; //B[5] is index of last 5
	}
	return null;
}

This function returns i, j for A[i] + A[j] = z; and it accounts of 5 + 5 = 10; Also returns null if fails.

Are all the inputs integers? You didn't say anything about type of input.

If we consider array A as sorted array then below code will work;

public static string Sum(int[] a , int z)
{
int i=0;
int len = a.length();
j=len-1;

while (a[i] +a[j] > z)
{
j--;
}
while(a[i]+a[j]<z)
{
i++;
}
if(a[i] + a[j] == z)
Console.Write("1st Indices {0} - 2nd Indices {1}", i,j);
else
Console.Write("Sum doesn't exists");
}

You should never assume an array is sorted (@ the other answers)

One way to do this is:

Pseduo-code:

public static int[]/*array? depending on your language*/ find(int [] A, int z/* , int k if exists*/)
{
	int i, size;
	/* //if k exists
	if (z > 2k) return null; // because you can't add 2 number from 1 to k to get anything <2, >2k
	size = k;
	*/
	size = z;
	int B[size] = {}
	for(i = 0; i < size; i++)
		B[i] = -1; //initialize B
	for(i = 0; i < A.length; i++) //you may not need A.length if you can't find it with your language, just exit when the array ends
	{
		if(A[i] >= z) continues; //if A[i] >=z, A[i] + a[j] > z

		if(B[z - A[i]] > 0) return {i, B[z-A[i]]};
		B[A[i]] = i; // this will make B[5] store the index for last 5, you can use an if too, but waste of comparison
	}
	return null; // if the function does not return in the for, there is no such pair.
}

public static int[] find(int[] A, int z /*,int k if k is given */)
{
	int i,size;
	int B[z]; // it best to do max of (k,z)
	/* //if k is given
	if (z > 2k) return null;
	for(i =0; i < z; i++) B[i] = -1;
	*/
	for(i = 0; i < A.length /* note */; i++) // or use true and break when you reach the end of the array if you can't get size of   A
	{
		if (A[i] >= z) continues; // useless number
		if(B[z-A[i]] > 0) return {i, B[z-A[i]]};
		B[A[i]] = i; //B[5] is index of last 5
	}
	return null;
}

This function returns i, j for A[i] + A[j] = z; and it accounts of 5 + 5 = 10; Also returns null if fails.

void test(){
		Integer a[] = {1,3,4,4,4,2,3,6};
		Integer z = 8;
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(Integer i = 0; i<a.length; i++){
			if(map.containsKey(z-a[i])){
				System.out.println(map.get(z-a[i])+"  "+i);
				break;
			}
			map.put(a[i], i);
		}
	}

void test(){
		Integer a[] = {1,3,4,4,4,2,3,6};
		Integer z = 8;
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(Integer i = 0; i<a.length; i++){
			if(map.containsKey(z-a[i])){
				System.out.println(map.get(z-a[i])+"  "+i);
				break;
			}
			map.put(a[i], i);
		}
	}

void test(){
Integer a[] = {1,3,4,4,4,2,3,6};
Integer z = 8;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer i = 0; i<a.length; i++){
if(map.containsKey(z-a[i])){
System.out.println(map.get(z-a[i])+" "+i);
break;
}
map.put(a[i], i);
}
}

void test(){
Integer a[] = {1,3,4,4,4,2,3,6};
Integer z = 8;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer i = 0; i<a.length; i++){
if(map.containsKey(z-a[i])){
System.out.println(map.get(z-a[i])+" "+i);
break;
}
map.put(a[i], i);
}
}

void test(){
Integer a[] = {1,3,4,4,4,2,3,6};
Integer z = 8;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer i = 0; i<a.length; i++){
if(map.containsKey(z-a[i])){
System.out.println(map.get(z-a[i])+" "+i);
break;
}
map.put(a[i], i);
}
}

/*
//We can use Hash Table to solve this problem. 
//First build a hash table for the array. Then for each element, find if z-A[i] is in the hash table. 
//However, it returns one possible pair. 
//But you can go through the whole array to get all pairs that satisfy A[i] + A[j] == z. Expected time is O(n).
*/
#include <stdio.h>
#include <iostream>
#include <unordered_map>

using namespace std;

bool ArraySum( int Array[], int N, int num );

int main( int argc, char* argv[] )
{
    int a[] = {1,2,3,4,5,6,7,8,9,0};
    int b[] = {-1,-2,-3,-5,-6,-7,-8,9,3,4,5,1,11};
    int n1 = 4;
    int n2 = 5;
    int n3 = -5;
    int n4 = 16;
    int n5 = 10;

    ArraySum(a, 10, n1);
    ArraySum(a, 10, n2);
    ArraySum(a, 10, n3);
    ArraySum(a, 10, n4);
    ArraySum(a, 10, n5);
    ArraySum(b, 13, n1);
    ArraySum(b, 13, n2);
    ArraySum(b, 13, n3);
    ArraySum(b, 13, n4);
    ArraySum(b, 13, n5);

    return 0;
}

bool ArraySum( int Array[], int N, int num )
{
    if( N <= 0 ) return false;
    unordered_map<int,int> HashTable;
    for( int i = 0; i < N; i++ )
     {
         pair<int, int> onePair(Array[i], i);
         HashTable.insert(onePair);
     }
    for( int i = 0; i < N; i++ )
    {
        if( HashTable.count(num-Array[i]) > 0 )
        {
            unordered_map<int, int>::const_iterator got = HashTable.find(num-Array[i]);
            if( got->first != i ) cout << "Array[" << i << "] + Array[" << got->second << "]" << " == " << num << endl;
            return true;
        }
    }
    return false;
}

The result is:

Array[0] + Array[2] == 4
Array[0] + Array[3] == 5
Array[6] + Array[8] == 16
Array[0] + Array[8] == 10
Array[0] + Array[10] == 4
Array[4] + Array[12] == 5
Array[1] + Array[2] == -5
Array[10] + Array[12] == 16
Array[0] + Array[12] == 10

The fact that k << n. Implies to me that instead of using hash map, I can use an int array of size k. This will be faster and efficient than using hash map although the logic is same.

Also if I have all the values [1,K] present in the array. I do not have to go till the end of this large array. I can count the number of unique entries and break as soon as I see that I have information for all K elements. This will save a lot of time. But if all the values are not present in the array then we have to go till the end.

Here is a sample code

package array;

import java.util.Arrays;

public class FindIndex {

	public static int[] findIndex(int[] a, int k, int z) {
		int[] result = new int[]{-1, -1};
		
		if(a.length == 0 || z > 2 * k) {
			return result;
		}
		
		int[] aux = new int[k];		
		int numElem = 0, i, j;
		
		for(j = 0; j < aux.length; j++) {
			aux[j] = -1;
		}
		
		for(i = 0; i < a.length; i++) {
			if(aux[a[i] - 1] == -1) {
				aux[a[i] - 1] = i;
				numElem++;
			}
			
			if(numElem == k) {
				// no need to traverse anymore. We have got all positions.
				break;
			}
		}
		
		System.out.println(Arrays.toString(aux));
		
		int val;
		for(i = 0; i < k; i++) {
			if(aux[i] != -1) {
				val = z - i - 1;
				
				if(val > k) {
					continue;
				}
				
				if(aux[val - 1] != -1) {
					result[0] = aux[i];
					result[1] = aux[val - 1];
					return result;
				}
			}
		}
		
		return result;
	}

	public static void main(String[] args) {

		int a[] = new int[]{1,5,2,4,3,5,4,3,2,1,1,3,2,4,5};
		int z = 4;
		int k = 5;
		
		int[] result = FindIndex.findIndex(a, k, z);
		System.out.println("The indices are "+ result[0] + " " + result[1]);

	}

}

Are all the inputs integers? You didn't say anything about type of input.