CareerCup

public void TargetSumMethod(int []numArray, int target)
	{
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		int lookup;
		for(int i=0; i<numArray.length; i++)
			hm.put(numArray[i], i);
		for(int i=0; i<numArray.length; i++)
		{
			lookup = target - numArray[i];
			if((hm.get(numArray[lookup])) != null)
			{
				System.out.println(numArray[i] + "+" + lookup );
			}
				
		}
	}

This should be in O(n)

///
i=0,j=n
while(i<j){
if(a[i]+a[j]>target)
j=j-1
if(a[i]+a[j]<target)
i=i+1
if(a[i]+a[j] == target)
print a[i],a[j]
i = i+1
j=j-1
///

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class TargetSum {

	public static void main(String[] args) {
		Integer array[] = {1, 2, 3, 4, 5, 1, 3};
		Integer target = 6;

		findPair(array, target);
	}
	public static void findPair(Integer[] array, Integer target) {
		Set<Integer> setArr = new HashSet<Integer> ();
        List<Integer> list = new ArrayList<Integer>();
        list = Arrays.asList(array);
        setArr.addAll(list);
        System.out.println("Pairs are : ");

        for (int i = 0; i < array.length && !setArr.isEmpty();  i++) {
        	System.out.println("i = " + i);
        	Integer temp = array[i];
        	Integer diff = target - temp;
        	setArr.remove(temp);
        	if(setArr.contains(diff)) {
        		System.out.println("(" + temp + ", " + diff + ")");
        		setArr.remove(diff);
        	}
        }
                    
	}
}

This will print all pairs (based on their indexes), even if we have repeating numbers , e.g.
[1,2,2,3],4
will print (1,3), (2,2).
[1,2,2,2,3],4
will print
(1,3),(2,2),(2,2),(2,2)

import java.util.HashMap;
import java.util.Map;

public class PairSum {
	public void printPairs(int[] arr, int target) {
		Map<Integer, Integer> elementCount = new HashMap<Integer, Integer>();
		for (int el : arr) {
			increaseElementCount(el,elementCount);
		}

		for (int el : arr) {
			Integer count = elementCount.get(target - el);
			if (count != null && count > 0) {
				int matchingPairs = count;
				if (isHalf(el, target)) {
					matchingPairs--;
				}
				for (int i = 0; i < matchingPairs; i++) {
					System.out.println("(" + el + "," + (target - el)+")");
				}
				int numberOfEl = elementCount.get(el);
				elementCount.put(el, --numberOfEl);
			}
		}
	}

	private void increaseElementCount(int el, Map<Integer,Integer> map) {
		Integer count = map.get(el);
		if (count == null) {
			count = 0;
		}
		map.put(el, ++count);
		
	}

	private boolean isHalf(int el, int target) {
		return (target == 2 * el);
	}
	public static void main(String[] args) {
		new PairSum().printPairs(new int[]{0,1,2,2,3,4}, 4);
	}
}

Either use hashing or sort and den check from start and end

#include<stdio.h>
#include<conio.h>
void printpairs(int arr[10],int target);
void main()
{
clrscr();
int arr[10],target;
printf("enter elements");
for(int i=0;i<10;i++)
{
scanf("%d",&arr[i]);
}
printf("enter target sum=");
scanf("%d",&target);
printf("pairs are");
printpairs(arr,target);
getch();
}
void printpairs(int brr[],int target)
{
int j,k;
for(k=0;k<10;k++)
{
for(j=k+1;j<10;j++)
{
if(brr[k]+brr[j]==target)
printf(" %d %d\n",brr[k],brr[j]);
}
}
}

any better optimized answers???

Is this array in sorted array?

findPair(int a[],int sum)
{
i=0;
j=n-1;

while( i<= j)
{
temp = a[i]+a[j];
if( sum == temp)
print(a[i],a[j])
else if( temp < sum)
i++
else
j--
}
}

since the question is not clear about if the array is sorted here are the solutions with both options:
1.) if the array is not sorted sort it in O(nlogn) and go to step 2 (if needed O(n) time with O(n) space you can use hashset over key = sum - arr[i] and then traverse the array and search if the value is in the hashset)
2.) if the array is sorted set two pointers in both ends and move the low++ or high-- depending on the sum requested. This is O(n)

here is Java implementation

public void printPair(int[] arr, int sum) {
  int low = 0;
  int high = arr.length - 1;
  
  while (low < high) {
   if (arr[low] + arr[high] == sum)
    System.out.format(“(%s, %s) ”, arr[low++], arr[high]);
   else if (arr[low] + arr[high] < sum)
    low++;
   else
    high--;
  }
 }

Initialize a temp list.
for every int in a[]
if(sum - a[i]) is present in list, print a[i] and sum - a[i]
else add a[i] to the list

I didn't compile... Just rough thought...

array.Sort(); // Sort array at first if permitted

int left = 0;
int right = array.Length - 1;

while (left <= right)
{
if (array[right] > target)
{
right--;
continue;
}

while (array[left] + array[right] <= target)
{
right--;
}

if (array[left] + array[right] == target)
{
push(left, right);
}

left++;
}

public static void findTargetSum(int[] pairsArr,int targetSum)
{
Map arrHashMap=makeHash(pairsArr);
int val;
for(int i=0;i<pairsArr.length;i++)
{
val=targetSum-pairsArr[i];
if(arrHashMap.containsKey((val)))
{
if(Boolean.valueOf(arrHashMap.get(val).toString())==true){
System.out.println(" valid answer:" +pairsArr[i]+","+(targetSum-pairsArr[i]));
}
}
arrHashMap.put(pairsArr[i],false);

}
}
public static Map makeHash(int[] pairsArr)
{
Map arrHashMap=new HashMap(pairsArr.length);
for(int i=0;i<pairsArr.length;i++)
arrHashMap.put(pairsArr[i],true);
return arrHashMap;
}

Doesn't handle the special case inputs EX 2,3,4,5,6,7,8 and target sum:10 displays 5,5

O(n):

void printPairs(int a[], int target){
			
		//start from left and right side of the array
		int left=0;
		int right=a.length-1;
		
		int toggle = 1;
		
		//continue until you meet
		while(left!=right){
			//if sum equals target print
			if(a[left]+a[right]==target){
				System.out.println("i=" + left+ "; j=" + right);
				left++;
				right--;
			} else {
				//use the toggle to move by one position
				//once for left, once for right, in turns
				if(toggle == 1){
					left++;
				} else {
					right--;
				}
				//switch the toggle
				toggle = 1 - toggle;
			}
		}
	}

static void findPair(final int a[], final int sum)
	{
		for (int i = 0; i < a.length; i++)
		{
			for (int j = i + 1; j < a.length; j++)
			{
				b++;
				if (sum == a[i] + a[j])
				{
					System.out.println(a[i] + "--" + a[j]);
				}
			}
		}
	}

static void findPair(final int a[], final int sum)
	{
		for (int i = 0; i < a.length; i++)
		{
			for (int j = i + 1; j < a.length; j++)
			{
				if (sum == a[i] + a[j])
				{
					System.out.println(a[i] + "--" + a[j]);
				}
			}
		}
	}

Here is what i would do

1. Sort the list[i] 1<=i<=n
2. Make a differencelist[i] = targetsum-list[i] 1<=i<=n
3.Do a binary search of each item in differencelist[i] on the list. If a match is found i.e differcelist[i]=list[k] where 1<=k<=n then you have a pair to make the target sum which is (list[i], list[k])

Complexity:
Sort - Best at O(nlogn)
Creating Difference list = O(n)
BInary Search for 1 element = logn
Binary search for n element = O(nlogn.)
Total complexity is O(nlogn)

Space Complexity-
O(2n)=>O(n)..

public static void TargetSum(int[] array, int target)
    {

      Dictionary<int, int> hashMap = new Dictionary<int, int>();

      int lookup = 0;     
     
      for (int i = 0; i < array.Length; i++)
      {
        lookup = target - array[i];

        if (hashMap.ContainsKey(lookup) == true)
        {
          Console.WriteLine("Pair {0},{1}", lookup, array[i]);

        }
        else
        {
          hashMap.Add(array[i], array[i]);
        }
      }



    }

#include <iostream>
#include <algorithm>
using namespace std;

void printPairs(int *a , int n ,int target){
int head = 0;
int tail = n - 1;
while ( head != tail ) {
if (a[head] >= target) break;
if ( a[head] + a[tail] == target )
{
cout << a[head] << " + " << a[tail] << " = " << target << endl;
head = head + 1;

}
else if (a[head] + a[tail] > target) tail = tail - 1;
else if (a[head] + a[tail] < target) head = head + 1;
}
}

int main() {

int A[10] = {10,12,1,5,3,4,7,6,2,8};
int n = sizeof(A) / sizeof(int);
sort(A, A + n);
int target = 11;
printPairs(A , n, target);
return 0;
}

How is this logic?

for i = 1 to 5
	for j = 1 to 5
		if i = j
		 continue
		else
		 if (a[i] + a[j] = target)
		   for k 1 to 5
		    if a[i] = c[k] and a[j] = b[k]
		     exist
		    else
		     doesnt exist
		    end if
		   end for
		   if doesnot exist
		   	move a[i] to b[n]
		   	move a[j] to c[n]
		   end if
		 end if
		end if
	end for
end for
print pair:
for i = 1 to 5
 print "(b(i),c(i))"
end for

#import<stdio.h>
#import<stdlib.h>
#import<string.h>
void findPairs(int *array,size_t len, int sum)
{
        int lookUp;
        int *a = (int*)malloc(sizeof(array));
        a = (int *)memcpy(a, array, sizeof(int)*len);
        for(int i = 0; i < len; i++)
        {
                if(a[i] == -1000)
                        continue;
                lookUp = sum - a[i];
                int j = 0;
                while(j < len)
                {
                        if(a[j] == lookUp)
                        {
                                printf("(%d, %d)", a[i], a[j]);
                                a[j] = -1000;
                                break;
                        }
                        j++;
                }
        }
}

int main()
{
        int a[] = {1, 2, 4, 3, 5};
        int target = 6;
        findPairs(a, (sizeof(a)/sizeof(int)), target);
}

A working Python Code

def getPairForSumN(item_list, N):
    hash_map = {}
    set_pair = set([])
    count = 0
    for item in item_list:
        hash_map[item] = N-item
    for k,v in hash_map.items():
        if hash_map.get(k,None) is not None and hash_map.get(hash_map.get(k, None) ) is not None:
            half_count = 0
            if N%2 == 0 and k == N/2:
                for each in item_list:
                    if each == k:
                        half_count += 1
                        if half_count >=2:
                            set_pair.add((k,v))
            else:
                set_pair.add((k,v))
            hash_map.pop(k)
                
            count += 1
    return set_pair