Solution to Problem 5 and some other thoughts about this type of questions

Since I posted the 5 programming problems every Software Engineer should be able to solve in less than 1 hour last night, the post has way over a thousand comments in Reddit and most of them are related to Problem 5.

Everyone agrees that the first 4 problems are relatively easy to solve (being Problem 4 a little bit more complicated), but apparently Problem 5 has multiple people wondering whether it can actually be completed under 1 hour (together with the other 4.)

Let's review the way I'd approach the problem and some Java code to solve it.

Solution to Problem 5

Here is the problem again, just in case you didn't read the previous post:

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

I think it looks harder than it really is. To solve it, I'd try to decompose the problem into smaller problems (you know, the classic Divide and conquer).

So let's start with what we know:

  • f(1..9) = 100

Here f is the function that returns our final equation. From here we can break this into 3 other pieces:

  • 1 + f(2..9) = 100
  • 1 - f(2..9) = 100
  • f(12, 3..9) = 100

The first equation uses an addition, the second uses subtraction, and the third equation concatenates the first two numbers. From here, we get the following:

  • f(2..9) = 100 - 1 = 99
  • f(-2, 3..9) = 100 - 1 = 99
  • f(12, 3..9) = 100

(Note how I moved the negative sign into the function on the second equation to keep the result the same.)

From here, we can keep working on each one of the equations above doing the same process:

  • 2 + f(3..9) = 99
  • 2 - f(3..9) = 99
  • f(23, 4..9) = 99
  • -2 + f(3..9) = 99
  • -2 - f(3..9) = 99
  • f(-23, 4..9) = 99
  • 12 + f(3..9) = 100
  • 12 - f(3..9) = 100
  • f(123, 4..9) = 100

You'd have to keep doing this until you completely eliminate the function f. From there, each branch where the equality holds represents a solution to the problem, so you can backtrack your steps to stitch the resultant equation together.

The source code

Of course nobody is going to follow the above solution manually, but it shouldn't be too hard to code it:

import java.util.ArrayList;

public class Main {

    private static int TARGET_SUM = 100;
    private static int[] VALUES = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    static ArrayList add(int digit, String sign, ArrayList branches) {
        for (int i = 0; i < branches.size(); i++) {
            branches.set(i, digit + sign + branches.get(i));
        }

        return branches;
    }

    static ArrayList f(int sum, int number, int index) {
        int digit = Math.abs(number % 10);
        if (index >= VALUES.length) {
            if (sum == number) {
                ArrayList result = new ArrayList();
                result.add(Integer.toString(digit));
                return result;
            }
            else {
                return new ArrayList();
            }
        }

        ArrayList branch1 = f(sum - number, VALUES[index], index + 1);
        ArrayList branch2 = f(sum - number, -VALUES[index], index + 1);

        int concatenatedNumber = number >= 0
            ? 10 * number + VALUES[index]
            : 10 * number - VALUES[index];
        ArrayList branch3 = f(sum, concatenatedNumber, index + 1);

        ArrayList results = new ArrayList();

        results.addAll(add(digit, "+", branch1));
        results.addAll(add(digit, "-", branch2));
        results.addAll(add(digit, "", branch3));

        return results;
    }

    public static void main(String[] args) {
        for (String string : f(TARGET_SUM, VALUES[0], 1)) {
            System.out.println(string);
        }

    }
}

This returns 11 possible solutions:

  • 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
  • 1 + 2 + 34 - 5 + 67 - 8 + 9
  • 1 + 23 - 4 + 5 + 6 + 78 - 9
  • 1 + 23 - 4 + 56 + 7 + 8 + 9
  • 12 + 3 + 4 + 5 - 6 - 7 + 89
  • 12 + 3 - 4 + 5 + 67 + 8 + 9
  • 12 - 3 - 4 + 5 - 6 + 7 + 89
  • 123 + 4 - 5 + 67 - 89
  • 123 + 45 - 67 + 8 - 9
  • 123 - 4 - 5 - 6 - 7 + 8 - 9
  • 123 - 45 - 67 + 89

(I'm sure there are better solutions to this problem. I'd love to see them, so please contact me if you have one.)

Can this actually be done in less than 1 hour?

Contrary to what some people think, there's no hidden trick on this problem or any special Math knowledge you have to know to solve it. This is a classic recursion problem that anybody with knowledge on the subject should be able to solve really quick.

Implementing it can be tricky, yes. If you are doing it in a whiteboard, of course it will be really difficult, but nobody said that whiteboard coding is a good thing.

A few more words about the previous post

A bunch of people got up in arms because exercises like this shouldn't be asked in an interview. I disagree.

As long as there are no hidden tricks, or special knowledge involved, or any other gotchas, I think these are perfectly valid questions to ask.

I never said that you'll be hired if you know how to answer these problems, but I won't consider you if you can't.

Everyone has a way. This is mine.

Update: More programming challenges

I love these type of programming problems. I'm going to try to publish one problem every weekend, hoping I'll have the time to find a good one and solve it myself. Here is the first one to celebrate Mother's Day: Programming challenge: rotating a matrix 90 degrees in place.

Please, get in touch with me and send me your favorite challenges.

Have something to say about this post? Get in touch!

Want to read more? Visit the archive.