2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Note the problem statement declares \$2\le n\le \color{red}{10^4}\$. Possibly it's not that fast (or safe) to go into recursion ten thousand levels deep...? I would try to organize the analysis at one level of call, e.g. by storing operators done and partial results in additional arrays and shifting an index to them forth and back. Once you reach the end of expression you can generate the output with a single scan through arrays of numbers and of operators. \$\endgroup\$ – CiaPan Oct 30 '17 at 16:07
2
\$\begingroup\$

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; } }

\$\endgroup\$
  • \$\begingroup\$ Note that the length of the output expression should not exceed 10 n, so that strategy might not work. \$\endgroup\$ – 200_success Oct 30 '17 at 19:09
  • \$\begingroup\$ @200_success 'N' is a number of operands, each value up to 100. That implies all numbers take up to 3N digits. Add N–1 operators and we have no more than 4N output characters. Add a space before and after each operator and that still makes less than 6N characters. So 10N is a fairly reasonable limit, and the strategy of placing operators has nothing to do with overflowing that. One would need to do something really silly to exceed 10N... \$\endgroup\$ – CiaPan Oct 30 '17 at 21:37
  • \$\begingroup\$ This is a cool analysis of the problem. \$\endgroup\$ – markspace Nov 30 '17 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.