Question: Given an integer array, find any 2 numbers which adds to a given integer. Return FALSE if no 2 such number exists.
Ex: array A[]= {3, 1, 8, 11, 5, 7}
given integer say N = 6
answer will be 1,5.
If N would be 5, answer will be FALSE.
Answer: A simple brute force approach may be to look for N-A[i] for every i from 0 to length of A. This will be an O(N^2) approach. If array is sorted, we can search N-A[i] in O(NlogN) time. Can we do better than this?
Not for unsorted array but for sorted array, we can certainly do better. It will add O(NlogN) time for sorting. (Time efficiency will be same as earlier binary search approach coz of sorting time but total number of comparison will be less.)
Algorithm:
Sort array A[] initialize 2 pointers. Start <= begining of the array A; end <= end of A while start < end if A[start] + A[end] < N increase start by 1 else if A[start] + A[end] == N return else decrease end by 1 end while return FALSE
Code:
bool sum_euqal_to_N(int A[], int N) { int start = 0; int end = MAX-1; //check for boundary conditions if ((A[start]+A[start+1]) > N) return false; if ((A[end]+A[end+1]) < N) return false; while (end > start) { if ((A[start] + A[end]) < N) start++; else if ((A[start] + A[end]) == N) { cout << A[start] << " " << A[end] << endl; return true; } else end--; } return false; }
Efficiency: if input array A is sorted then O(N).
else O(NlogN) coz of sorting time NlogN.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
using a hash table will enable you to get O(n). for a given input array,store 10-a[i] as a key and value as a[i].do this for the whole array.now for a given element in array a[i] check if the hash table contains a[i] as key.
@Anonymous: Space Complexity is O(n) and you have assumes O(1) operations in hash.
Nice solution! Writing too much code in higher level languages make me try to solve problems more efficiently by using the languages features that end up increasing space complexity @_@ (bad habit)
line 8 and 11 should be return FALSE;
line 8 and 11 should be return FALSE
I don't think it will find the answer when A=[1 2 4 6], N=5.
Ah, my bad. It will work.