Pages

Tuesday, March 23, 2010

PROBLEM: Find two numbers in an array that sum to a magic number value

import java.util.Hashtable;

public class ArrayNumberSum {

    public static void main(String[] args) {
        int magicNumber = 16;
        int[] intArray = new int[] { 1, 12, 10, 4, 5, 7 };
        int[] result = calculate(intArray, magicNumber);

        System.out.println("Two values that add up to " + magicNumber + " are " + result[0] + " and " + result[1] + ".");

    }

    /**
     * Ideally to solve this problem, we will create a hashtable that keep as Key the array[i] and the value
     * the difference between the array[i] and the magicNumber.
     * 
     * Once the difference is equal to a key, it means we found the two numbers.
     */
    static int[] calculate(int[] n, int magicNumber) {
        int[] result = new int[2];
        Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();

        for (int i = 0; i < n.length; i++) {
            int diff = magicNumber - n[i];
            int key = n[i];

            if (!table.containsKey(key) // just to perform better
            ) {
                table.put(key, diff);

                // check if one key is equal to my difference values
                if (table.containsKey(diff)) {
                    result[0] = diff;
                    result[1] = key;
                    break;
                }
            }
        }

        return result;
    }
}

No comments :