 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member Join Date
Dec 2015
Posts
4

## 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 -> 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?  Reply With Quote

2. ## Re: Interesting Problem

The algorithm for a basic math problem? Must be school.  Reply With Quote

3. Junior Member Join Date
Dec 2015
Posts
4

## 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.  Reply With Quote

4. Banned  Join Date
Jun 2015
Posts
208

## 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.  Reply With Quote

5. Junior Member Join Date
Dec 2015
Posts
4

## 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.  Reply With Quote

6. Banned  Join Date
Jun 2015
Posts
208

## 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 public-key cryptography works. Also see NP-completeness.

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.  Reply With Quote

7. Junior Member Join Date
Dec 2015
Posts
4

## Re: Interesting Problem

Thank you, tiliavirga for your answer. It is mathematical division,like 7 / 3 = 2.(3)  Reply With Quote

8. Banned  Join Date
Jun 2015
Posts
208

## 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 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).

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.  Reply With Quote

algorithms, mathematics, problems #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 