How to represent a number with given numbers using arithmetic operations?

Question

This is an interview question. "Given an array of numbers and another number, work out whether the array of numbers can be manipulated using standard mathematical techniques to equal the other number given. e.g. given 5 and 10, can you make 50? 5 * 10 = 50, so yes". (Let's assume only arithmetic operations for simplicity).

I would propose to use a brute-force search (with some branch and bound). Does it make sense ?

Answer 1

Programming in Haskell, Chapter 11: The countdown problem

Answer 2

A very important first question is: Are any unary operations allowed? That is, can I change x into -x, 1/x, x!, or sqrt(x) "for free"?

If so, a naive branched search won't terminate, since there is no a priori bound on the number of uses of unary operations. If not, a naive search may work just fine.

Here's a fun strategy, if not an efficient one: Ask for, or produce, a BNF grammar for the arithmetic in use. Hack in a rule like

< unit > ::= 5 | 10

and then use that grammar to develop all possible expressions obtained using, say, less than 20 grammatical rules. Evaluate them all. That will be guaranteed to be bounded, and will generate all "not-too-complex" expressions valid in the language.

Answer 3

Another way to solve this would be by using genetic algorithms. Your population would start out as random operators inserted between the elements of your array.

Let S be the number you need to get to. Your fitness function could be |S - Value(E[i])|, where Value(E[i]) is the value after evaluating the i-th expression in your population.

Your mutation operator could simply change one operator to another, and your crossover function could combine the operators from the left of an expression with those from the right of another expression.

Maybe you can find more sophisticated functions that work better, genetic algorithms require a bit of guess work for best results.

I have no idea how this would compare to brute force, but it's a different solution and I think it would make you stand out in an interview, since everyone will be able to see the brute force solution.

If you only need a good enough solution (something that's not exactly S, but close enough), then this should definitely be faster than brute force. In the few genetic algorithms I've implemented I noticed that they rapidly approach a solution that's close to optimal, but are rather slow and sometimes even get stuck if you want the optimal solution.

Answer 4

I would ask

• Are the Numbers integers?
• Is there an upper limit to the scale of the numbers?
• Which standard mathematical techniquesare meant?
  • only simple arithmetic?
  • roots, powers?
  • reciprocals?
  • trig functions?

etc

Answer 5

I think this makes sense.

You can take advantage of symmetry between multiplication to further prune your tree. a * b = b * a.

Answer 6

Brute force sounds like a valid way to approach this. But brute force is uninformed search...it doesn't make educated guesses at which path to take when you reach a branch in the search tree.

What you may want to look into is whether there are heuristic functions that can help you make your search informed. A heuristic function looks at a state and gives an estimate of how far away you are from the goal. If you can find a valid heuristic function, you can apply an algorithm like A*.

Be warned: this doesn't seem to be an easy problem for which to define a heuristic.