Arrays4

Q4. Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Answer:

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

public class Arrays4 {
    public static void printPairs(int[] a, int sum) {
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) {
            if (!m.containsKey(a[i])) {
                m.put(a[i], 0);
            }
            m.put(a[i], m.get(a[i]) + 1);
        }

        for (Integer data : m.keySet()) {
            int dataCount = m.get(data);
            // run the loop till we have count for data greater than 0
            while (dataCount > 0) {
                dataCount = m.get(data) - 1;
                m.put(data, dataCount);

                // find complement of data in the map
                int complement = sum - data;

                // if count for complement is greater than 0
                // then print a pair and reduce count for complement
                int complementCount = (m.get(complement) == null) ? 0 : m.get(complement);
                if (complementCount > 0) {
                    System.out.println(data + " " + complement);
                    complementCount = m.get(complement) - 1;
                    m.put(complement, complementCount);

                    // break the loop if there is no more complement
                    if (complementCount == 0) {
                        break;
                    }
                }
            }
        }
    }

    public static void printPairs2(int[] a, int sum) {
        Arrays.sort(a);

        int first = 0;
        int last = a.length - 1;

        while (first < last) {
            // if we get a pair. print it
            // increase first and decrease last
            if ((a[first] + a[last]) == sum) {
                System.out.println(a[first] + " " + a[last]);
                first++;
                last--;
            } else if ((a[first] + a[last]) < sum) {
                first++;
            } else {
                last--;
            }
        }
    }

    public static void main(String[] args) {
        int[] a1 = { 3, 4, 3, 4, 1, 6, 1, 6, 6 };
        System.out.println("Pairs of sum 7 for array a1: ");
        printPairs(a1, 7);

        int[] a2 = { 1, 2, 3, 4, 5 };
        System.out.println("Pairs of sum 7 for array a2: ");
        printPairs(a2, 7);

        int[] a3 = { 3, 3, 3, 3, 3 };
        System.out.println("Pairs of sum 6 for array a3: ");
        printPairs(a3, 6);

        System.out.println("Pairs of sum 7 for array a1: ");
        printPairs2(a1, 7);

        System.out.println("Pairs of sum 7 for array a2: ");
        printPairs2(a2, 7);

        System.out.println("Pairs of sum 6 for array a3: ");
        printPairs2(a3, 6);
    }
}