Hackerrank: Arithmetic Expressions

The main thing you are missing is that when total is 0 (a multiple of 101), you can stop the recursion and just make all other operators be *, as you already reached a multiple of 101 and product will keep it like that.

As for the order of operators in the recursive function, the right choice is to put * at the end, which seems to be what you have right now. The main reason is that 101 is prime, so you won´t get a multiple of 101 by the products of numbers. So it´s better to leave that choice for last, as + or - have higher chances of generating a multiple of 101 quicker.

Update: I have tried your resursion solver with the stopping when reaching to 0 remainder but it still gives time out in a few cases, so ended up trying a different approach: dynamic programming.

The trick is that 101 is small, so the possible remainders are only between 0 and 100. The idea is that when looking at the ith number, you don´t really care if the accumulated result from previous operations is 2 or 103 or 204, you only care that its remainder with 101 is 2.

With that in mind, we can make a boolean array where we will store the remainders that can be generated by a combination of operations using the previous numbers.

So for each of these remainders we can get with the previous numbers (0 to i - 1 ), the remainders we could possibly get in the ith step are the same but adding, substracting and multiplying the ith number by that remainder.

I decided to keep a 2 dimensional array, where the first dimension is the step and the second one the remainder: boolean[][] remainders = new boolean[10000][101];

So for each number in the array, if we are on the ith step we iterate remainders[i - 1] and look for the true values. For those, we set the new remainders[i][j + array[i]], remainders[i][j - array[i]], remainders[i][j * array[i]] to true.

Note that we need to add modulo to that to keep it between 0 and 100.

The complexity of this is N * 100. Considering worst case, 10^4 * 100 = 10^6 which should fit nicely in the given time.

With this done, we know for each step what remainders we can get. So according to the problem, remainders[array.length - 1][0] should always be true as it can always be obtained.

There is still the problem that we don´t know what operation we used for each step so we can´t reconstruct the operations just by storing these values in remainders. I suggest you to think over how to do this.

If you still can´t manage, here is my full code that passed the tests. I don´t usually use java so my code surely has some improvements to make.

        import java.io.;
        import java.util.;
        import java.text.;
        import java.math.;
        import java.util.regex.;

        public class Solution {

            static int array[];

            public static void main(String[] args) {
               Scanner s = new Scanner(System.in);
               int n = s.nextInt();
               array = new int[n];
               for (int i = 0; i < n; i++)
                   array[i] = s.nextInt();
               System.out.println(solve());
            }


            public static String solve () {
                boolean[][] remainders = new boolean[10000][101];
                Character[][] operators = new Character[10000][101];
                int[][] previousRemainder = new int[10000][101];

                remainders[0][array[0]] = true;


                for (int i = 1; i < array.length; i++) {
                    int num = array[i];

                    if (remainders[i - 1][0]) {
                        remainders[i][0] = true;
                        operators[i][0] = '';
                        previousRemainder[i][0] = 0;
                    } else {
                        for (int j = 0; j < 101; j++) {
                            if (remainders[i - 1][j]) {
                                remainders[i][Math.floorMod(j + num, 101)] = true;
                                operators[i][Math.floorMod(j + num, 101)] = '+';
                                previousRemainder[i][Math.floorMod(j + num, 101)] = j;

                                remainders[i][Math.floorMod(j - num, 101)] = true;
                                operators[i][Math.floorMod(j - num, 101)] = '-';
                                previousRemainder[i][Math.floorMod(j - num, 101)] = j;

                                remainders[i][Math.floorMod(j * num, 101)] = true;
                                operators[i][Math.floorMod(j * num, 101)] = '*';
                                previousRemainder[i][Math.floorMod(j * num, 101)] = j;
                            }
                        }
                    }

                }

                String result = Integer.toString(array[0]);
                Integer currentRemainder = 0;
                String[] operatorsResult = new String[10000];

                for (int i = array.length - 1; i >= 1; i--) {
                    operatorsResult[i] = Character.toString(operators[i][currentRemainder]);
                    currentRemainder = previousRemainder[i][currentRemainder];
                }

                for (int i = 1; i < array.length; i++) {
                    result += operatorsResult[i] + Integer.toString(array[i]);
                }

                return result;


            }
        }