CareerCup

Use set for an O(n) solution. For space constraint sort the input and get a solution in O(nlgn) as bellow:

//O(n) with O(n) space
public static void getPairs(int[] input, int sum)
{
	HashSet<Integer> h = new HashSet<Integer>();
	
	for(int i=0;i<input.length;i++)
	{
		if(h.contains(sum-input[i]))
			System.out.println(“Pair: (”+input[i]+”, ”+sum-input[i]+”)”);
		h.add(input[i]);
	}
}

//O(nlgn) with O(1) space
public static void getPairs(int[] input, int sum)
{
	input = sort(input);
	int start = 0;
	int end = input.length-1;
	StringBuilder sb = new StringBuilder();

	while(start<=end)
	{
		if(input[start]+input[end] == sum)
			sb.append(“(”+input[start]+”, ”+input[end]);
           else if(input[start]+input[end] >  sum)
	           end--;
           else start++;	
	}
	
	System.out.println(sb.toString());
}

/*
Creates a hash map with key as the sum and a hash set of number pairs(as lists)
Running time: O(n^2) 
*/

package com.puzzles;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class PairFinder {
	public static HashMap<Integer,HashSet<List>> findPairs(Integer[] arr){
		int i,j,sum;
		HashMap<Integer,HashSet<List>> sumMap=new HashMap<Integer,HashSet<List>>();
		int len=arr.length;


		for(i=0;i<len-1;i++){
			for(j=i+1;j<len;j++){
				List<Integer> pair=new ArrayList<Integer>();
				pair.add(arr[i]);
				pair.add(arr[j]);
				sum=arr[i]+arr[j];
				if(sumMap.containsKey(sum)){
					sumMap.get(sum).add(pair);
				}
				else{
					HashSet<List> sumSet=new HashSet<List>();
					sumSet.add(pair);
					sumMap.put(sum, sumSet);
				}

			}
		}
	return sumMap;
	}
	public static void main(String[] args){
		Integer[] arr={1,2,3,4,3};
		HashMap<Integer,HashSet<List>> sumMap=findPairs(arr);
		Set<Integer> sumSet=sumMap.keySet();
		Iterator<Integer> itr = sumSet.iterator();
		while(itr.hasNext()){
			Integer key=itr.next();
			HashSet<List> pairs=sumMap.get(key);
			System.out.println("sum: "+key+" ; pairs:"+pairs.toString());
		}
		
	}
}

Malformed question detected

Take 1 min. next time to show an example.

1) Build hashmap of the array (or sort the arrray) for part 1
Complexity O(N) in case of hashmap and O(nlogn) in case of sort
2) Use 2 loops and hashmap to find out all unique values of sum possible
3) Find the different between sum of min 2 elements (sum1) and max 2 elements(sum2) and let it be D. If D<<N, then iterate from sum1 to sum2 to find various values of sum possible.

public class TwoSum {
// find pairs whose sum to target
public static ArrayList<ArrayList<Integer>> solution(int[] num, int target){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

if(num == null || num.length < 2){
return result;
}

Arrays.sort(num);

int before = 0;
int after = num.length - 1;

while(before < after){
int sum = num[before] + num[after];
if(sum < target){
before++;
}else if(sum > target){
after--;
}else{
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[before]);
temp.add(num[after]);
result.add(temp);

do{
before++;
}while(before < after && num[before] == num[before - 1]);

do{
after--;
}while(before < after && num[after] == num[after + 1]);
}
}

return result;
}

// find all pairs' sum in an array
public static ArrayList<Integer> findAllValue(int[] num){
ArrayList<Integer> result = new ArrayList<Integer>();
HashSet<Integer> values = new HashSet<Integer>();

for(int i = 0; i < num.length - 1; i++){
for(int j = i + 1; j < num.length; j++){
values.add(num[i] + num[j]);
}
}

for(Integer value: values){
result.add(value);
}

return result;
}

// display pairs in an ArrayList
private static void display(ArrayList<ArrayList<Integer>> list){
for(ArrayList<Integer> pair: list){
System.out.println(pair);
}
}


public static void main(String[] args){
int[] num = {1,4,1,4,2,3};

ArrayList<Integer> values = TwoSum.findAllValue(num);

for(Integer value: values){
System.out.println(value);
ArrayList<ArrayList<Integer>> result = TwoSum.solution(num, value);
TwoSum.display(result);
System.out.println();
}
}
}

package org.devil.ds.array;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *	@Purpose Given an array, print all the pairs that sum to a particular value. You are not given the value, find all possible values and print pairs for them
 */
public class ArrayElementPairSum {
	private static class Pair{
		int p1;
		int p2;
		public Pair(int p1, int p2){
			this.p1 = p1;
			this.p2 = p2; 
		}
		
		@Override
		public int hashCode(){
			return Integer.valueOf(p1 +p2).hashCode();
		}
		@Override
		public boolean equals(Object obj){
			return obj!=null ? obj.hashCode() == this.hashCode()  ?  p1 == ((Pair)obj).p1|| p1== ((Pair)obj).p2? true : false : false :false;
			}
		@Override
		public String toString(){
			return " [ "+this.p1+", "+this.p2+" ]";
		}
	}
	public static void main(String[] args) {
		
	int[] nums ={1,2,3,4,5,6,7,8,9};
	
	Map<Integer,Set<Pair>> resultMap = new HashMap<>();
	int outerCount = 0;
	for(int i :nums) {
		int innerCount = 0 ;
		for(int j:nums){
			
			if(outerCount == innerCount++){
				continue;
			}
			int sum = i+j;
			Set<Pair> holder = resultMap.get(sum);
			if(holder == null) {
				holder = new HashSet<>();
			} 
			if(holder.add(new Pair(i,j)))			
				resultMap.put(sum,holder);
		}
		outerCount++;
	}

	System.out.println(resultMap);
	}
}

Any non n^2 algorithms?

def sum_pairs(inp):
    d = {}
    for i in inp:
        for j in inp:
            if ((i != j) and ((j,i) not in d)):
                print i, j, " sum: ", i+j
            d[(i,j)]=True

sum_pairs([1,2,3])

nlogn (to sort) + n*logn (n elements * binary search = logn) = nlogn