We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #93: Arithmetic expressions

# Project Euler #93: Arithmetic expressions

#### Sort by

recency

#### |

#### 11 Discussions

#### |

Please Login in order to post a comment

import java.util.*;

public class LongestSequence { private static final double EPSILON = 0.00001;

}

This one is the first problem which I find the HackerRank version is easier than the default question, but maybe only because I hadn't evaluated a better algorithm yet.

The original involves finding the longest chain when M=4, which could mean checking every 4 digit combination. This gives you a combination and asks you to find its max length, significantly less computation.

After finding a way to generate every partition of the combination, and then a recursive means of evaluating all the potential values of any combination, and then dealing with some floating point rounding, it wasn't so bad. I wonder if the original question would still be harder.

Brackets can be understood as which one you calculate together. If you generate all possible sub-groups, the problem is same as not have brackets.

My approach was

GenerateCombinatations of give size(starting with 4) with given input (starting with all 10 digits)

We need to work on each of these but we can again use same method to generate more combinations of size 3. Then same method to generate more combination of size 2.

Perform all operations whenever you have group of size two, you get six possibilities:

a+b , a*b, a-b , b-a , a/b , b/a,

you need to use floating point numbers. Recombine the results, recalculated till group size reduces to 1. When are at a single answer at this to result set of the topLevelGroup. Find max sequence number in each result set.

Two observations that may help:

1) A somewhat simple and algorithmical way to consider every parenthesis grouping is generating and evaluating every valid

Postfix Expression.2) If you use floating point numbers, limited precission gives wrong answers for some tests. An alternative to using more precission, maybe a little more messy, is solving it using

only integer numbers. That can be achieved if you use (integer) numerators and denominators in the operations (for example, you can implement a rational number class with two integer fields and all four operations)you can find my java solution here