CareerCup

Time complexity is O[n]

Go through from head and tail to middle. Sum array[head index] and array [tail index] to tell which it meet requirement. If small, move head index with +1. If big, move tail index with -1

What if the question was asking about 3 numbers that sum to a given number?

you can subtract arr[i] from value and search for difference in rest of array using binary search. This will have complexity of O(nlog(n).

//arr = 0,1,2,3,4,5,7,8,9
//sum = 10
//sub = 10,9,8,7,6,3,2,1
//-------------------------------
arr[]={0,1,2,3,4,5,7,8,9};
val = 10;
int n = arr.length;
if(arr[0] == 0)
{
	if(val != 0)
	{
		int i = bsearch(arr, val, 0, n-1);
		if(i!= -1)
		{
			print i,val ;
			return;
		}
	}
	else
	{
	  print arr[0],val;
	  return;
	}
} else
{
	array sub = nrw array[n-1];
	for(int ctr=0; ctr < (n-1); ctr++) 
	{
		var temp = arr[ctr];
		sub[ctr] = val - temp;
		int num = bsearch(arr, sub[ctr], 0, n-1);
		print num, temp;
		return;
	}
	
}

//arr = 0,1,2,3,4,5,7,8,9
//sum = 10
//sub = 10,9,8,7,6,3,2,1
//-------------------------------
arr[]={0,1,2,3,4,5,7,8,9};
val = 10;
int n = arr.length;
if(arr[0] == 0)
{
	if(val != 0)
	{
		int i = bsearch(arr, val, 0, n-1);
		if(i!= -1)
		{
			print arr[i],val ;
			return;
		}
	}
	else
	{
	  print arr[0],val;
	  return;
	}
} else
{
	array sub = new array[n-1];
	for(int ctr=0; ctr < (n-1); ctr++) 
	{
		var temp = arr[ctr];
		sub[ctr] = val - temp;
		int num = bsearch(arr, sub[ctr], 0, n-1);
		print arr[num], temp;
		return;
	}
	
}

iterate in the array with low starting from 0 and high from aray.length -1
in each iteration
-->if we find the sum return both the elements, array[low] and array[high]
->if the sum of array[low] and array[high] is less than sum increment low, low++
-->else decrement high, high --

private static void findTwoElementsSumUpToN_inGivenSortedArray(final int[] a, final int n) {
		int i = 0, j = a.length - 1, sum = 0;
		while (i < j) {
			sum = a[i] + a[j];
			if (sum > n) {
				j--;
			} else if (sum < n) {
				i++;
			} else {
				System.out.println(a[i] + "," + a[j]);
				break;
			}
		}

}

* Given a sorted array find two num that sum to given number */
void findelementsthatsum(int *array, int length, int sum)
{
        int head = 0;
        int tail = length - 1;
        int temp = 0;

        while (head <= tail)
        {
                temp = array[head] + array[tail];
                if (sum > temp) head++;
                if (sum < temp) tail--;
                if (sum == temp) printf("\nTHe needed pair is :%d, %d", array[head++], array[tail]);
        }
}

int N = 2 +4;
    static const int ar[] = {1,2, 4, 6, 7, 11, 3343, 22331};
    int size = sizeof(ar)/sizeof(ar[0]);
    const int* oldlow = ar + size;
    for(int i = 0; i < size; ++i)
    {
        int a = ar[i];
        const int* low = std::lower_bound(ar, oldlow, N - a);          
        if((low == oldlow) || (*low + a) != N)
            continue;
        else
        {
            if(a > *low)
                break;
            std::cout << a << " " << *low << std::endl;
        }
        oldlow = low;
    }

int[] in = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i ,j,n;
n = 10;

for (i = 0, j = in.length - 1; j > i; i++, j--) {
if (in[i] + in[j] > n)
j--;
else if (in[i] + in[j] < n)
i++;
else
System.out.println("Pair(i+j=n) = ("+(i+","+j)+"="+n+")");
}

Simple Binary Search Logic will work.. since it is a sorted array. Complexity is O(log n).

Input: sum and a sorted array.
Idea: you select the larger of the two numbers and find a smaller matching number.

Approach:
1.) Find the largest number in the array that is smaller than sum. You wouldn't require to go beyond this index to search for the sum. Save the index as 'maxInd'.
2.) Now go backwards from 'maxInd' till index 1 OR 'sum' - '[current value in array]' is less than the '[current value in array]'. There is no point in selecting larger number which cannot add up to sum with a smaller number.
[You can store the index of the previous 'smaller' number which you had found. You need not reconsider this number again. Since, you would have already found a pair that contains the value at that index.]
2.1) Now starting from 'prev index'+1 till 'maxInd'-1,
2.1.1) if current value in array equals 'sum' - '[current value in array]' store the current index as 'prev index' print out the larger and the current number.
2.1.2) break; and continue with loop in step 2.)

eventually you would have found all the pairs that sum up to the given sum.
Space complexity O(1). Time complexity, O(n).

Above approach could be easily modified to be a reccursive version with space complexity as O(m[m is the number of integers to find]) and time complexity as O(nxm).