rahul.goswami0206
BAN USER/*
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());
}
}
}
Awesome solution! I don't think you need to take compliment of the final xor though...taking xor of all the elements of the two arrays adhering to the constraints mentioned by yyang.even gives the correct output
- rahul.goswami0206 January 28, 2016