Finding the number of distinct pairs of integers that sum up to an integer

I am trying to count the numbers of pairs in an array such that each pair gives the sum of an integer!

I used the following code :

    public static int SumPairs(Integer []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
    int tmp=0;
    //System.out.println(pairs.toString());
     for(int i=0;i<input.length;i++){
     if(pairs.containsKey(input[i])){
            System.out.println(pairs.containsKey(input[i]));
             System.out.println(input[i] +", "+ pairs.get(input[i]));
             input[i]=0; 
            tmp++;      

        }

        else
            pairs.put(k-input[i], input[i]);
    }return tmp;
}

the problem is ; for example when my array is 1 2 2 2 3 4 4 4 and sum = 5 it compute as following

(4,1)
(4,1)
(4,1)
(3,2)

I want to prevent the method from using a number more than once !! so the output will be

(4,1)
(3,2)

Answer

I use a map storing values and their frequencies:

public static int SumPairs(Integer[] input, int k){
    Map<Integer, Integer> frequencies = new HashMap<>();
    int pairsCount = 0;      

    for(int i=0; i<input.length; i++){
        int value = input[i];
        int complement = k - input[i];

        if(frequencies.containsKey(complement)){                
            int freq = frequencies.get(complement) - 1;
            pairsCount++;
            //System.out.println(value + ", " + complement);    
            if(freq == 0){
                frequencies.remove(complement);
            }else{
                frequencies.put(complement, freq);
            }
        }else{
            if(frequencies.containsKey(value)){         
                frequencies.put(value, frequencies.get(value) + 1);             
            }else{
                frequencies.put(value, 1);
            }
        }
    }
    return pairsCount;
}

Advertisement

Answer