mf-Tech

A question was asked to me the other day, one which put me on the spot and got me thinking. I’m not a math wizard, by any means, but I have heard of things in passing over my couple years in the programming field.

The question asked had to do with Big-O Notation. Here is the question:

Say you have an arbitrary length array of numbers. The type of numbers in this array is irrelevant. There can be duplicates, but again, irrelevant. If you given a random number, how would you determine if the array contained two numbers which summed to this random number.

So being asked this, I instantly said, well, loop through the array (and you would have to do this twice) to figure out which numbers added together equaled this passed in number. This would be an example of O(n^2). I was told by the person asking the question, “you’re right, but how would you improve on this”. This is when I started to draw a blank.

As I went through the scenario again, I told myself, if that array was HUGE say 1 million numbers, that would take forever to figure out. After trying to deciper how I would program it in Java talking out ideas like “if I put it in a Map, but how would I determine key/value” or “if I put it in a list, no, that’s not really making any sense” and “I could divide, no, that’s not right”. Finally, I decided to throw in the towel. I was told that the answer would be something that improved on O(n^2).

Let me say this now, I’m not a Math major. I’ve taken the token Algebra, Pre-Calculus, etc. I’d like to get a Computer Science degree someday, but currently my motivation is elsewhere. So to be asked a question like this, without prior knowledge, is extremely daunting. So that night, I really didn’t think about it more, I decided I would try to look it up the next day when I had time and see what it was. At least that’s what I wanted to do.

Until this morning, at around 6:30am, when it hit me. Could it be this simple? Why didn’t I see this when he asked. So now I’ll show you what I came up with in about an hour or so of coding (I did take another hour to error check, etc after I verified it worked). It may not be bullet proof, but I know it works. FYI, I don’t have a compiler or IDE on the computer I’m at, but I found an online compiler for Java and the computer I’m on has a Java6 JRE on it. The Java source file is attached at the end of the post.

Basically we want to loop through the collection once, determine the difference between the passed in number and the value from the array. We’ll store these values in a Map (hashtable) then move on. Everytime we compute a difference, we’ll check the Map to see if we’ve found one of the values (either the difference or array value). If we find it, then we’ll pop out of the loop and return it. Now for the bulk of the heavy lifting code in Java:

public void findNumberSum(int[] numberArray, int sumToFind,
  boolean stopAtFirst) {

  Map foundNumbers = new HashMap();

  // Loop through the array, but we'll only need to do it once, due to
  // using a HashMap - O(n) rather than O(n^2)
  int i = 0;
  while (i < numberArray.length) {
    int arrVal = numberArray[i];

    int diff = sumToFind - arrVal;
    //System.out.println("sumToFind[" + sumToFind + "] - arrVal["
    //  + arrVal + "] = diff[" + diff + "]");

    foundNumbers.put(String.valueOf(diff), String.valueOf(arrVal));

    // If the map contains either of the values, in this case the
    // difference of the sumToFind and the number from the array or the
    // actual number from the array, then we've found a match, check
    // stopAtFirst to break and return the first match back or continue
    // on your way listing all matches.
    if (foundNumbers.containsKey(String.valueOf(diff))
      && foundNumbers.containsValue(String.valueOf(diff))) {

      System.out.println("Found a set! [" + arrVal + ", " + diff + "]");

      if (stopAtFirst) return;
    }

    i++;
  }
}

So that’s it. Anyway, this was a long post, but I needed to get it out there. If you have some comments, or various suggestions to make my thrown together code more effiecient or better, please drop a comment.

Here is my full Java source for this problem: Test Array Example