Find Two Numbers in an Array that Sum to a Particular Value

talk open source
1

So, while working on my Dictionary/Hashtable tutorial, I decided to create a more interesting example that many of you may have encountered. Basically, given a huge list of numbers, the goal is to find two numbers from that list that sum up to a particular value.

I provide an example and a more elaborate description in this [U]link[/U]. The code for it is:

//Declaring a Dictionary
Dictionary<int, int> numberHash = new Dictionary<int, int>();
 
//Collection of Integers
int[] values = { 144, 29, 46, 55, 33, 64, 174, 144, 168, 129, 73, 186, 24, 163, 3, 165, 160, 79, 39, 3, 81, 175, 183, 175, 15, 150, 177, 191, 29, 106, 104, 56, 58, 85, 172, 72, 119, 192, 134, 11, 10, 54, 34, 27, 194, 182, 71, 183, 132, 147, 23, 78, 70, 13, 144, 93, 104, 177, 181, 62, 155, 26, 50, 172, 158, 17, 139, 156, 105, 26, 162, 15, 65, 30, 174, 62, 175, 182, 121, 56, 23, 77, 179, 161, 168, 36, 25, 46, 137, 178, 51, 21, 65, 41, 78, 71, 196, 142, 78, 33, 130, 81, 55, 15, 131, 145, 135, 99, 116, 104, 20, 6, 22, 201, 135, 29, 148, 71, 110, 20, 104, 89, 105, 1, 10, 9, 53, 92, 75, 112, 161, 106, 196, 60, 163, 102, 109, 182, 148, 56, 88, 47, 151, 22, 119, 97, 163, 77, 126, 16, 151, 112, 143, 15, 76, 133, 124, 49, 114, 36, 183, 64, 4, 129, 201, 197, 161, 46, 103, 36, 58, 2, 78, 199, 113, 97, 53, 149, 60, 78, 63, 50, 152, 150, 140, 113, 101, 85, 80, 123, 186, 78, 95, 105, 195, 74, 121, 44, 40, 94, 149, 34, 74, 78, 28, 166, 126, 132, 51, 15, 200, 147, 77, 170, 171, 67, 67, 52, 57, 198, 186, 152, 69, 43, 194, 12, 37, 157, 144, 128, 153, 168, 130, 121, 186, 200, 195, 192, 162, 180, 95, 94, 24, 39, 37, 131, 177, 103, 106, 62, 28, 110, 145, 67, 99, 98, 137, 56, 26, 10, 56, 152, 36, 195, 150, 3, 87, 193, 16, 128, 186, 67, 122, 196, 162, 24, 56, 12, 2, 160, 190, 84, 17, 13, 112, 11, 200, 177, 120, 26, 33, 23, 11, 176, 7, 160, 49, 177, 92, 186, 176, 161, 175, 92, 30, 172, 186, 142, 145, 76, 44, 15, 171, 56, 158, 3, 9, 172, 92, 54, 101, 197, 158, 191, 102, 157, 32, 193, 156, 164, 74, 10, 106, 91, 176, 32, 132, 69, 197, 188, 184, 109, 5, 160, 200, 116, 55, 93, 143, 26, 82, 140, 52, 176, 120, 198, 178, 125, 122, 201, 44, 56, 96, 96, 29, 175, 156, 113, 17, 18, 70, 158, 159, 193, 162, 153, 40, 67, 170, 177, 182, 40, 78, 192, 173, 151, 55, 110, 142, 155, 56, 1, 134, 134, 50, 189, 105, 158, 34, 51, 17, 98, 131, 158, 89, 57, 158, 82, 112, 95, 149, 78, 60, 31, 144, 27, 94, 4, 45, 88, 152, 157, 82, 188, 73, 67, 198, 199, 198, 123, 201, 20, 171, 8, 115, 66, 144, 190, 126, 108, 5, 12, 14, 147, 35, 52, 139, 108, 57, 2, 128, 54, 157, 145, 75, 34, 26, 63, 201, 124, 198, 42, 109, 153, 177, 47, 173, 150, 3, 143, 198, 167, 110, 66, 20, 151, 147, 115, 108, 191, 142, 123, 169, 17, 127, 197, 86, 39, 144, 10, 165, 36, 151, 179, 185, 75, 39, 86, 194, 3 };
 
//Value to Guess
Random randomNum = new Random();
int x = randomNum.Next(10, 200);
 
//Trying to find two numbers that, when added, equal the sum
for (int i = 0; i < values.Length; i++)
{
    int currValue = values*;
    if (!numberHash.ContainsKey(currValue)) {
        int diffValue = x - currValue;
        numberHash.Add(currValue, diffValue);
        if (numberHash.ContainsKey(diffValue)) {
            Console.WriteLine("Two values that add up to {0} are {1} and {2}", x, currValue, diffValue);
            break;
        }
    }
}

[SIZE=2]As you can see, the code behind it is fairly simple. The ideas behind it have applications beyond this particular example, for there are many useful things you can do when storing/retriving data is really fast.[/SIZE]
[SIZE=2][/SIZE]
[SIZE=2]Just copy and paste that into a main method in VS2005 or another IDE and find out which two numbers in the array sum up to a value determined during runtime. You can also choose to run the attached file after extracting it. Whatever works :beam:

Cheers!
Kirupa :)[/SIZE]

2

I wrote the following that will find if m number of elements add to make a sum of k. The complexity is O(n) (or O(m * n) since there are m comparisons for each element, which is still linear time).

The code is in Java and assumes that Pair<A, B> is already implemented:


    public static boolean findN(Integer[] a, int n, int k) {
        Hashtable<Pair<Integer, Integer>, Pair<Integer, Integer>> hash = new Hashtable<Pair<Integer, Integer>, Pair<Integer, Integer>>();
        for (int i = 0; i < a.length; i++) {
            int curr = a*;

            for (int j = 1; j < n; j++) {
                // no need to check the nth case for a full match on just currs,
                // because if n is even, n/2 case would match itself and if n
                // was odd the n/2 and (n + 1)/2 cases would match
                Pair<Integer, Integer> value = new Pair<Integer, Integer>(curr
                        * j, j);
                Pair<Integer, Integer> diffValue = new Pair<Integer, Integer>(k
                        - curr * j, n - j);
                if (hash.containsKey(diffValue) || value.equals(diffValue)) {
                    System.out.println("There are " + n
                            + " values that add up to " + k + "!");
                    return true;
                }
                if (!hash.containsKey(value)) {
                    hash.put(value, diffValue);
                }
            }
        }
        System.out.println("No values add up");
        return false;
    }
4

While looking at referrer logs, I noticed that leetcode has this problem listed and people googled for similar terms and landed here! I don’t even remember much of C# these days haha :stuck_out_tongue: