Hackerrank: Arithmetic Expressions Problem: Arithmetic expressions


  Given a list of 2..10,000 integer numbers in a range of 1..100 place operators +, - or/and * between them, so that the whole expression results in a number divisible by 101. Output the resulting expression.
  Note, the operators have no precedence and are left-associative: expression a+b*c-d*e shall be interpreted as (((a+b)*c)-d)*e.


Link

import java.io.*;
import java.util.*;

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 &lt; n; i++)
           array[i] = s.nextInt();
       System.out.println(array[0] + recursive(array[0], 1));
    }

    public static String recursive(int total, int index) {
       total %= 101;
       if (index == array.length){
           return total == 0 ? "" : null;
       }
       String result =recursive(total-array[index],index +1);
       if (result != null){
          return "-" + array[index] + result;
       }
          result = recursive(total + array[index], index + 1);
       if (result != null){
          return "+" + array[index] + result;
       }
       result = recursive(total * array[index], index + 1);
       if (result != null){
          return "*" + array[index] + result;
       }
       return null;
    }
}


I have tried multiple submissions with alternating the sequence of '+','-','*' and also tried same solution in C but always get the "Terminated due to timeout" message. I am the end of my thinking capacity and would appreciate any help possible.

Note: Changing the sequence of '+','-','*' in recursive function check helped me with few test cases during each sequence , but didn't pass all the test cases for any sequence.
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 &lt; 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 &lt; 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 &lt; 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 &lt; array.length; i++) {
                    result += operatorsResult[i] + Integer.toString(array[i]);
                }

                return result;


            }
        }