Printable View
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 -> 7-3-2*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?
The algorithm for a basic math problem? Must be school.
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.
You can always check every possible combination.Quote:
Originally Posted by Vlad_Dohotaru
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.
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 public-key cryptography works. Also see NP-completeness.Quote:
Originally Posted by Vlad_Dohotaru
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
Thank you, tiliavirga for your answer. It is mathematical division,like 7 / 3 = 2.(3)
There is no such thing as "mathematical" division in some divine God-given 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).Quote:
Originally Posted by Vlad_Dohotaru
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.