Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

Problem

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Strategy

This problem requires every element in the list to be checked against every other element at least once. In the worst case scenario, we will have to check:

• 1 pair for 2 elements
• 3 pairs for 3 elements
• 6 pairs for 4 elements
• etc.

These are triangular numbers. The Nth triangular number T(N) is given by:

    T(N) = N * (N + 1) / 2

So this algorithm has a worst-case time complexity of N². Assuming the list has N elements...

• The first element should be checked against the second through Nth elements
• The second element should be checked against the third through Nth elements
• etc.

As soon as a pair is found that adds up to k, we can quit. We don't need to find all pairs, we just need to find the first pair that adds to k. The problem states that the pair shouldn't be returned, just true or false.

Code

The first thing I would do is build a double for loop, where the outer loop moves over all elements of the list (except the last) and the inner loop moves over all elements after the current element of the outer loop. Assuming the given list is called given

int[] given = new int[]{ ... };
int k = ...;

int len = given.length;

for (int outer = 0; outer < (len - 1); ++outer) {
  for (int inner = outer + 1; inner < len; ++inner) {

    // ... logic here

  }
}

This way, we compare no two elements twice.

The only thing left to do is check if the elements at indices outer and inner add to k. If they do, we're done -- we can return true. Otherwise, we check the next pair. If we get through all pairs without finding any which sum to k, we return false:

int[] given = new int[]{ ... };

int len = given.length;

public boolean codingProblem001 (int[] array, int k) {

  for (int outer = 0; outer < (len - 1); ++outer) {
    for (int inner = outer + 1; inner < len; ++inner) {

      if (given[outer] + given[inner] == k)
        return true;

    }
  }

  return false;
}

Let's check this to see if it works:

$ jshell
|  Welcome to JShell -- Version 9.0.4
|  For an introduction type: /help intro

jshell> /open DCP001.java

jshell> int[] given = new int[]{ 10, 15, 3, 7 }
given ==> int[4] { 10, 15, 3, 7 }

jshell> int k = 17
k ==> 17

jshell> DCP001.codingProblem001(given, k)
$4 ==> true

jshell> DCP001.codingProblem001(given, k+1)
$5 ==> true

jshell> DCP001.codingProblem001(given, k+2)
$6 ==> false

Result $4 is true because 10 and 7 add to k. $5 is also true because 15 and 3 add to k+1. But $6 is false because no two elements of given add to k+2.

All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.