7
$\begingroup$

Given a set of numbers (in this case):

3, 7, 7, 100, 50

Either:

prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + 7) * 100)

or

find the expression that does form the number k = 190.

I am not sure how to work on this problem analytically as the general case of any subset and any number k appears to be an NP Hard problem.

I wish to brute force the solution for this. Is the following algorithm sufficient:

Take set F: Compute all possible ordered subsets of F (How to do this elegantly?)

Compute all possible combinations of operators between each ordered subset...

If any equal 190 then the problem is solved, if none equal 190 then clearly its not possible.

How do I generally design this algorithm? Is there a better way to solve this problem (preferably without brute force)?

My attempt at analytics:

I wanted to see if by working with the number modulo Q it would be easy to filter out which possible expressions may evaluate to 190. Since the expression S = 190 must be true mod Q for all Q if it is true.

My other attempt at brute force:

Starting from 190, systematically, add, subtract, divide, etc... expressions from the original set in the hope that one of these expressional chains concludes in a value that is still present in the set. This seems to be as computationally expensive as the previous method (How would I implement this?)

$\endgroup$
  • $\begingroup$ Are repetitions allowed: For example $100/100 = 1$ and $190 = 1 + 1 + \dots + 1 $? $\endgroup$ – hot_queen May 2 '13 at 22:44
  • $\begingroup$ Only elements from the set used once, if there are 3 5's u can use 5 up to 3 times $\endgroup$ – frogeyedpeas May 2 '13 at 23:20
  • 2
    $\begingroup$ I think this might be what you're looking for: sysexpand.com/?path=exercises/expression-from-numbers $\endgroup$ – Jebdm Jan 11 '14 at 7:16
3
$\begingroup$

I saw this riddle somewhere before, and I think it should be numbers 3 7 7 8 50 100 given (you probably missed number 8), and then the solution for this is:

( 50 - 8 ) * 7 - 100 - 7 + 3 = 190

:)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.