
December 10th, 2015, 05:44 AM
#1
Interesting Problem
Given an array of n numbers,develop a deterministic algorith that will say if it is possible or not to insert between each two numbers one of the operators "+", "", "*"(multiplication), "/"(division),such as the result of the expression would be equal to 0.
Example:
1)7 3 2 2 > 732*2 => Success
2)7 3 5 11 > no possible combination => FAIL
Do you know an algorith for this problem or have an idea how to solve it?

December 10th, 2015, 01:02 PM
#2
Re: Interesting Problem
The algorithm for a basic math problem? Must be school.
ahoodin
To keep the plot moving, that's why.

December 10th, 2015, 01:37 PM
#3
Re: Interesting Problem
The brute solution will be very expensive since time complexity if i check all the possibilities will be 4^n,and that too much i think. I am interested in finding something more efficient.

December 10th, 2015, 02:22 PM
#4
Re: Interesting Problem
Originally Posted by Vlad_Dohotaru
Do you know an algorith for this problem or have an idea how to solve it?
You can always check every possible combination.
In the example there are 4 numbers in between which there are 3 places to put any of 4 operators. So the total number of combinations to will be 3^4 = 81. It can easily be done with 3 fixed nested loops or recursively to a depth of 3.

December 10th, 2015, 02:55 PM
#5
Re: Interesting Problem
What if the input will be 100 numbers? Isn't there a more efficient solution? checking every possible combinationt obviously does not work for a greater amount of numbers as input.

December 10th, 2015, 09:37 PM
#6
Re: Interesting Problem
Originally Posted by Vlad_Dohotaru
What if the input will be 100 numbers? Isn't there a more efficient solution? checking every possible combinationt obviously does not work for a greater amount of numbers as input.
There may not exist a more efficient solution. Some problems simply have no solution (in polynominal time). That's why publickey cryptography works. Also see NPcompleteness.
I suspect your problem may be one of those very hard intractable problems (with the disclaimer that I've been wrong before ). To know for sure the approach is to show that ones problem is equivalent to one of the known standard hard problems. If that's the case any hope of finding an efficient solution is gone and only small inputs can be solved within a reasonable time.
By the way, your problem is underspecified. You haven't defined what kind of division / is. If it's the integer division you find in most programming languages your second example could evaluate to 0 like this,
7 / 3 / 5 / 11 = 0
Last edited by tiliavirga; December 12th, 2015 at 01:52 AM.

December 12th, 2015, 08:32 AM
#7
Re: Interesting Problem
Thank you, tiliavirga for your answer. It is mathematical division,like 7 / 3 = 2.(3)

December 12th, 2015, 01:25 PM
#8
Re: Interesting Problem
Originally Posted by Vlad_Dohotaru
It is mathematical division,like 7 / 3 = 2.(3)
There is no such thing as "mathematical" division in some divine Godgiven sense. In every specific case algebraic operations must be defined. With your definition of division you have effectively graduated your problem from the natural numbers to the real numbers. Then, since a digital computer is finite, you also need to be more specific about what you mean by 0 (or rather 0.0).
Anyway, just like nature has put a cap on the speed of light it has put a cap on computing (quite fascinating I think). Some problems simply are intractable. It's important to be aware of this to avoid wasting time on futile solution attempts. Unfortunately to actually prove intractability isn't the easiest of things. The most common approach is to show that a problem is equivalent to another problem that's already been proved intractable. But this is PhD stuff so one usually has to rely on intuition.
Last edited by tiliavirga; December 14th, 2015 at 03:13 AM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
