CareerCup

By assuming array elements are sorted in ascending order, below is the algorithm(which will take care of duplicate elements as well).

void All_Sum_Pair(int A[], int start, int end, int SUM)
{
    int temp = 0;
    if(start<end){
        temp = A[start] + A[end];
	if(temp == SUM){
	    print("(%d, %d), ",A[start], A[end]);
            All_Sum_Pair(A, start+1, end, SUM);
	    All_Sum_Pair(A, start, end-1, SUM);
	} else if(temp > SUM){
	    All_Sum_Pair(A, start, end-1, SUM);
	} else {
	    All_Sum_Pair(A, start+1, end, SUM);
	}
    }
}

I think by "pairs" he means just 2 nos. summing to the value of N.

Store the values in a HashMap. Iterate over each value "x" in the array and find N-x in the HashMap. If found, you got a pair, store it in a HashSet (this will eliminate duplicates).
Time: O(n)

Solution in Python

def FindPairs(array,N):
map={value:index for index,value in enumerate(array)}
pairs={(elem,N-elem) for elem in map if N-elem in map and elem>=N-elem}

Time Complexity - O(n)

2 pointer approach. one starts at the end of the array and other at the end.

1) if sum ( a[first pointer] , a[second pointer]) > N move second pointer left
2) if sum ( a[first pointer] , a[second pointer]) < N move first pointer right

keep moving untill 2 pointers meet each other.

I'm thinking about {1,2,2,2,3} N=4
Let me rewrite the array to {1,2a,2b,2c,3}
Shall we return (1, 3) (2a, 2b) (2a, 2c) (2b, 2c) ?

This code also takes care of duplicates, unlike most of the solutions given here

arr=[0, 1, 2, 2, 3, 4, 5]
N = 4
map = {}
for num in arr:
    if N-num in map:
        print((num, N-num))
    map[num] = True

How long do you think that it's appropriate to think about this question ? And how long to write it?

The pairs only contain 2 numbers? Can it have more or less than two numbers?

for(int j=0;j<=num-1;j++)
{
int val=i[j];
int temp=num2-val;
for(j=0;j<=num-1;j++)
{

if(temp==i[j])
System.out.println("["+val+","+temp+"]");
}

1. if you sort the array , then the running time is at least 0(nlogn).
2. Is all the number positive ?
if it was, we could count the appearance of 0,1,...N in O(n) running time, and let p(i) be the frequency of i , since 0+N==N,1+(N-1)==N,...then we have min(a(i),a(N-i)) pairs of (i,N-i);
if there're negative numbers, in O(n) running time(the first scannning) we can get each of them,and you can store its frequency too, the remaining similar. While you may scan the array twice, you still got the 0(n) running time.

#include <stdio.h>
#define MX 7 //max no of array
//target is value sum value
//let assume given array sequence[MX] ={0, 1, 2, 2, 3, 4, 5};//assuming array is not sorted
int main()
{
int array[MX];
for(count = 0; count<MX;count++)
{
array[MX] = 0;
}
for(count = 0; count<MX;count++)
{
array[sequence[count]] = 1;
}
for(count = 0; count<MX;count++)
{
index = target - sequence[count];
if(index > 0)
{
if(array[index] == 1)
{
print(pair(sequence[count],index));
array[index] = 0;
array[sequence[count]] = 0;
}
}
}
return 0;
}

complexity : 0(n)

public class PrintPairsThatSumUpToValueInArray {

public static void main(String[] args) {
PrintPairsThatSumUpToValueInArray pps = new PrintPairsThatSumUpToValueInArray();
int[] array = { 8, 0, 1, 2, 2, 3, 3, 3, 4, 5, 1, 4, 6, 4, 4, 4, 5 };
int TARGET_SUM = 10;
Map<Integer, Integer> map = pps.loadMap(array);
pps.printPairsFromMap(TARGET_SUM, map);
}

public Map loadMap(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
for (int val : array) {
if (map.containsKey(val)) {
int count = (Integer) map.get(val);
map.put(val, ++count);
} else {
map.put(val, 1);
}
}
return map;
}

public void printPairsFromMap(int targetSum, Map<Integer, Integer> map) {
Iterator<Integer> itr = map.keySet().iterator();
while (itr.hasNext()) {
int key = itr.next();
int value = map.get(key);
if (key > targetSum)
continue;
int diff = targetSum - key;

if (!map.containsKey(diff))
continue;
else if (key < diff) {
System.out.println("(" + key + "," + diff + ")");
} else if (key == diff && value > 1) {
System.out.println("(" + key + "," + diff + ")");
}
}
}

}

public static void main(String[] args) {
final Map<Integer, Integer> values = new HashMap<Integer, Integer>();
final Map<Integer, Integer> sumOfPair = new HashMap<Integer, Integer>();

final int targetVal = 4;
int key = 0;
final int[] arrayOfNums = { 0, 1, 2, 2, 3, 4, 5 };
for (int i : arrayOfNums) {
values.put(key, i);
if ((values.containsValue(targetVal - i)) && ((targetVal - i) != i)) {
sumOfPair.put(i, (targetVal - i));
}
key++;
}
Iterator<Map.Entry<Integer, Integer>> entries = sumOfPair.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.print("(" + entry.getKey() + "," + entry.getValue()+") ");
}
}

void printPair(int arr[],int size,int sum)
{
map<int,int> traversed;
map<int,int>::iterator it;
int i , remain;
for (i = 0 ; i < size ; i++)
{
remain = sum - arr[i];
it = traversed.find(remain);
if (it != traversed.end() && it->second > 0)
{
cout << "\n(" << it->first << "," << arr[i] << ")" ;
traversed.erase(it);
}
if(it != traversed.end())traversed[arr[i]]=1;
else (it->second)++
}

}

Assuming the array is sorted the following algorithm also works -

N - being the given sum.

1] Find x = sum(first , last)
2] if x = N print elts[first] and elts[last] and continue till u reach half the array.
if x < N then first++
if x > N then last--

public static void main(String[] args) {
		
		int[] elts = {0, 1, 2, 2, 3, 4, 5};
		int N = 4;
	
		for (int i = 0,j=elts.length-1; i < (elts.length/2) && i!=j ;) {
			if (elts[i]+elts[j] > N)
				j--;
			else if (elts[i]+elts[j] < N)
				i++;
			else {
				System.out.println("(" + elts[i] + " , " + elts[j] + ")");
			    j--;
			}
		}

public static void main (String args[]){

int[] num = {0, 1, 2, 2, 3, 4, 5};
int input = 4;
find(num,input);

}

public static void find(int[] num, int input){

for(int i=0;i<num.length;i++){
for(int j=0;j<num.length-1;j++){

if(num[j]+num[i]==input){

System.out.println(num[i]+ " " +num[j] + " "+ input);
}


}
}


}

Sorting the array will give better time complexity than O(n^2). We can assume thant sorting is O(nlogn) + Iteration of the elements which are less than N (arr[i] + arr[j] < N) - I can not say how much time it takes, but I believe that it is better than O(n^2)

public class SumOfNums {
	public static void main(String[] args) {
		int[] arr = { 0, 1, 2, 2, 3, 4, 5 };
		int N = 4; // (x+y==4 ?)

		// sort the array
		Arrays.sort(arr);
		int i = 0;
		while (i < arr.length-1) {
			int j = i+1;
			while (j < arr.length - 1 && arr[i] + arr[j] < N) {
				j++;
			}
			if (arr[i] + arr[j] == N)
				System.out.print("(" + arr[i] + "," + arr[j] + "), ");
			i++;
		}
	}
}

Time Complexity = N^2

void findPair(int arr[], int size, int target, map<int, int> &data)
{
	for(int i=0; i<size; i++)
	{
		int find = target - arr[i];

		for(int j=i; j<size; j++)
		{
			if (find == arr[j])
			{
				pair<int, int> p(arr[i], arr[j]);
				data.insert(p);
				break;
			}
		}

		if ( arr[i] + arr[i+1] >= target)
			break;
	}

}

here is the best simple solution:

public void findpairs(int ary[], int sum){
map<int,int>find=new hashmap<int,int>();
int i;
for(i=0;i<ary.length();i++){
find.put(ary[i],sum-ary[i]);
}
for(i=0;i<ary.length();i++){
if(find.containsValue(ary[i]){
system.out.println("here are the pairs",+ary[i],sum-ary[i]);
}
else{
system.out.println("sorry no pairs");
}
}
}

In Python

def SumPairs(arr,num):
    return [(each,num-each)for each in arr if (num-each)>0 and (num-each) in arr]

Time complexity: Worst case: (n)
Space complexity: If we want distinct pairs then Worst case: (n) else its O(1).

External methods used:
1.) void sort(int array[]); //QUICK SORT avg case running time is nlog(n)
2.) int search(int array[], int key, int lowerBound, int upperBound); //BINARY SEARCH. returns the index of the found element.

Additional datastructures:
1.) implementation of Set interface. //This is to check duplicates.

public void printPairs( int array[], int sum){

MySet set = new MySet();
int remainder;
int found = false;
int lowerBound = 0;

sort(array);
for( int i = array.length -1; i >= 0; i--){

if(k > array[i]){

remainder = k - array[i];
int index = search(array, remainder, lowerBound, i);

if(index > -1){
found = true;

if(!set.contains(Math.abs(array[i] - array[index]))){

System.out.print( "("+array[i] + ",(" + array[index] + ") ");
set.add(Math.abs(array[i] - array[index]));
lowerBound = index;
}
}
}
}

if(!found){
System.out.println("Sorry no pairs found.");
}
}

The set stores the absolute difference between the pairs. the difference and the sum (i.e. k) uniquely identifies the pair (idea is that, Xi + Yi = m, Xi - Yi = n, Xj + Yj = m and Xj - Yj = n, then i = j).

The lowerBound( prevents the binary search to check for previously checked lower numbers of the array.

int find(int a[],int start,int end,int num){
    while(start<end){
                     if(a[start]+a[end]==num){
                          printf("(%d,%d) ",a[start],a[end]);                    
                          start++;
                     }
                     else if(a[start]+a[end]>num){
                          end--;
                     }
                     else{
                          start++;
                     }
    }
}

import java.util.ArrayList;
import java.util.List;

public class Test {
	public static void main(String[] args) {
		
		int[] values = {0,1,1,2,3,4,5,6};
		int target = 6;
		outer: for(int i= 0; i<values.length; i++){
			int sum = values[i];
			List<Integer> sequence = new ArrayList<Integer>();
			sequence.add(sum);
			inner: for(int j = (values.length -1); j>i;j--){
				 sum = sum+values[j];
				if(sum > target){
					sum = sum-values[j];
					continue inner;
				} else if(sum <= target){
					sequence.add(values[j]);
					if(sum == target){
						System.out.println(sequence);
						sum = values[i];
						sequence.clear();
						sequence.add(values[i]);
					}
				}
			}
			
		}
	}
}

Time Complexity = O(logN), if its sorted Array
package careerCupJava;

public class SumWith2Numbers {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int arry[] = {0,1,2,2,3,4,5};
int i=0, j=arry.length - 1;
System.out.println("j="+j);
int sum=4;
while(i <= j)
{
int k = sum-arry[i];
if(k == arry[j])
{
System.out.println("pair pair="+arry[i]+arry[j]);
i++;
j--;
}
if( k < arry[j])
{
j--;
}
}

}

}

# include <stdio.h>
# include <conio.h>

void all_sum_pair(int a[10],int start, int end, int suma)
{
 int tempa=0;
 if(start < end)
 {
	tempa = a[start]+a[end];
	if(tempa == suma)
	{
		printf("(%d, %d), ",a[start],a[end]);
		all_sum_pair(a, start+1, end, suma);
	}else{
		all_sum_pair(a, start, end-1, suma);
	}
 }

}

void main ()
{
int arr[10];
int i,nn,j,temp,sum;
nn=10;
sum=5;

printf("Enter 10 Numbers in a column\n");

for(i =0; i <10;i++)
{
	scanf("%d",&arr[i]);
}



for(i=1;i<nn;i++)
{
	for(j=i;j>0 && arr[j]<arr[j-1];j--)
	{
		temp=arr[j];
		arr[j]=arr[j-1];
		arr[j-1]=temp;
	}
}
 for (i=0; i<10;i++)
	printf("%d\n",arr[i]);

all_sum_pair(arr,0,nn-1,sum);

printf("completed");
getch ();

clrscr();
}

public class PairNumber {
public int[] array =new int[]{0,1,2,3,4,5);
public void displayPairNumber(int value){
array ={0,1,2,3,4,5);
for (int i=0;i++;i<=value){
n=value;
if (i+n=value){

System.out.println(array(i)+,+array(n));
}
if (n==i){
break; } } }

Algo goes like this. Assuming array is sorted

1. point 1 reference to start of the array say i, 2nd reference to the end of the array say j
2. if a[i] + a[j] == N print pairs, else if a[i] + a[j] > N j-- else if a[i] + a[j] < N i++ till i < j

Thinking of better approach for un-sorted array