The Score of Students Solving Math Expression

Hard Dynamic Programming Interval DP Original on LeetCode

Reported atFlipkart

The Score of Students Solving Math Expression is a hard dynamic programming problem solved with the interval dp pattern. The best approach, optimal (interval dp over capped value sets), runs in O(n³ · V²) worst case time and O(n² · V) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every split recursively) up.

Problem

A teacher writes an expression s made of single digits joined by + and * (no spaces, no brackets) and collects the students’ results in answers. The correct result follows normal precedence: every * is done before any +.

Grading: an answer equal to the correct result earns 5 points. Otherwise, an answer earns 2 points if it can be produced by evaluating the operators in some wrong order, that is, by some way of fully parenthesising s and computing it with exact arithmetic. Any other answer earns 0.

Return the total number of points over all answers.

Examples

Example 1

Input
s = "3+2*4", answers = [11, 20, 11, 7]
Output
12
Why
The correct value is 3 + 8 = 11 (5 points each, twice). Grouping as (3 + 2) * 4 gives 20 (2 points). 7 is unreachable (0 points).

Example 2

Input
s = "6*2+1", answers = [13, 18, 12, 0]
Output
7
Why
13 is correct (5). 6 * (2 + 1) = 18 is a wrong-order result (2). 12 and 0 cannot be produced by any grouping.

Example 3

Input
s = "1+1*0", answers = [1, 0, 2]
Output
7
Why
Correct value 1 + 0 = 1 earns 5; (1 + 1) * 0 = 0 earns 2; 2 earns nothing.

Constraints

  • 3 <= s.length <= 31; s alternates single digits 0–9 and the operators + / *, starting and ending with a digit.
  • At most 15 operators.
  • The correct value of the expression is between 0 and 1000.
  • 1 <= answers.length <= 10^4; 0 <= answers[i] <= 1000.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every split recursively)O(Catalan(n) · V²)O(n · V)
Optimal (interval DP over capped value sets)O(n³ · V²) worst caseO(n² · V)

1Brute force (try every split recursively)

TimeO(Catalan(n) · V²)Without memoisation the number of recursive calls grows like the Catalan numbers in the operand count n; each combine is up to V² pairs (V ≤ 1001).
SpaceO(n · V)Recursion depth n, each level holding a set of at most V values.

Compute the correct value with normal precedence. Then, for the whole expression, recursively pick every operator as the last one applied, compute all values of the left side and right side, and combine them. No caching, so the same sub-expression is solved many times.

  1. Evaluate s with precedence: keep a running product, add it to the sum at each +.
  2. results(lo, hi): one digit returns itself; otherwise for each operator k between lo and hi, combine every value of results(lo, k - 1) with every value of results(k + 1, hi), keeping values <= 1000.
  3. Score each answer: 5 if it equals the correct value, else 2 if it is in results(0, n - 1), else 0.
class Solution {
    public int scoreOfStudents(String s, int[] answers) {
        long correct = evaluate(s);
        Set<Integer> all = results(s, 0, s.length() - 1);
        int score = 0;
        for (int a : answers) {
            if (a == correct) score += 5;
            else if (all.contains(a)) score += 2;
        }
        return score;
    }

    private long evaluate(String s) {
        long sum = 0, prod = s.charAt(0) - '0';
        for (int i = 1; i < s.length(); i += 2) {
            int d = s.charAt(i + 1) - '0';
            if (s.charAt(i) == '*') prod *= d;
            else { sum += prod; prod = d; }
        }
        return sum + prod;
    }

    private Set<Integer> results(String s, int lo, int hi) {
        Set<Integer> out = new HashSet<>();
        if (lo == hi) { out.add(s.charAt(lo) - '0'); return out; }
        for (int k = lo + 1; k < hi; k += 2) {
            Set<Integer> left = results(s, lo, k - 1), right = results(s, k + 1, hi);
            for (int a : left)
                for (int b : right) {
                    int v = s.charAt(k) == '+' ? a + b : a * b;
                    if (v <= 1000) out.add(v);
                }
        }
        return out;
    }
}

2Optimal (interval DP over capped value sets)

TimeO(n³ · V²) worst casen²/2 intervals, n splits each, and at most V × V value pairs per split (V = 1001); real sets are far smaller and the early break prunes most pairs.
SpaceO(n² · V)One value list of size at most V for every interval.

Same recursion, but bottom-up over operand intervals so each interval's value set is built once. Keep every set as a sorted list of distinct values in [0, 1000]: values never decrease when combined (except * 0, which gives 0), so once a combination passes 1000 the rest of the sorted right list can be skipped.

  1. Let the operands be d[0..n-1] (n = s.length / 2 + 1); the operator between d[m] and d[m+1] is s[2m + 1].
  2. vals[i][i] = [d[i]].
  3. For each interval [l, r] by increasing length: for every split m in [l, r), combine each a in vals[l][m] with each b in vals[m+1][r]; mark a + b or a * b in a boolean array of size 1001, breaking out of the b loop once the value exceeds 1000. Collect the marked values in order.
  4. Compute the correct value with normal precedence (use 64-bit: a long run of 9s before a * 0 can be huge).
  5. Score: 5 for the correct value, 2 for any other value in vals[0][n-1], else 0.
class Solution {
    public int scoreOfStudents(String s, int[] answers) {
        int n = s.length() / 2 + 1;
        int[][][] vals = new int[n][n][];
        for (int i = 0; i < n; i++) vals[i][i] = new int[] { s.charAt(2 * i) - '0' };
        for (int len = 2; len <= n; len++)
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                boolean[] seen = new boolean[1001];
                for (int m = l; m < r; m++) {
                    boolean plus = s.charAt(2 * m + 1) == '+';
                    for (int a : vals[l][m])
                        for (int b : vals[m + 1][r]) {
                            int v = plus ? a + b : a * b;
                            if (v > 1000) break;
                            seen[v] = true;
                        }
                }
                int cnt = 0;
                for (boolean x : seen) if (x) cnt++;
                int[] list = new int[cnt];
                for (int v = 0, k = 0; v <= 1000; v++) if (seen[v]) list[k++] = v;
                vals[l][r] = list;
            }
        boolean[] possible = new boolean[1001];
        for (int v : vals[0][n - 1]) possible[v] = true;
        long correct = evaluate(s);
        int score = 0;
        for (int a : answers) {
            if (a == correct) score += 5;
            else if (possible[a]) score += 2;
        }
        return score;
    }

    private long evaluate(String s) {
        long sum = 0, prod = s.charAt(0) - '0';
        for (int i = 1; i < s.length(); i += 2) {
            int d = s.charAt(i + 1) - '0';
            if (s.charAt(i) == '*') prod *= d;
            else { sum += prod; prod = d; }
        }
        return sum + prod;
    }
}

Edge cases to test

  • Only one kind of operator: every grouping gives the same value, so no answer earns 2 points
  • A * 0 that wipes out a huge intermediate product
  • An answer equal to the correct value must get 5, never 2 (the correct value is also a reachable grouping)
  • Intermediate results above 1000 can be dropped: no answer is that large and values never shrink except by * 0, which yields 0 anyway

Hints

Hint 1

The correct value is ordinary evaluation: multiply runs of *, then add the runs.

Hint 2

A 'wrong order' result is the value of SOME full parenthesisation. The last operator applied splits the expression into a left part and a right part.

Hint 3

Store the set of reachable values for every substring of operands (interval DP). Since answers never exceed 1000 and values only grow, cap every set at 1000.

FAQ

What is the best time complexity for The Score of Students Solving Math Expression?

Optimal (interval DP over capped value sets) runs in O(n³ · V²) worst case time and O(n² · V) extra space. n²/2 intervals, n splits each, and at most V × V value pairs per split (V = 1001); real sets are far smaller and the early break prunes most pairs.

Which pattern does The Score of Students Solving Math Expression use?

It is a dynamic programming problem that uses the interval dp pattern. Other problems with the same pattern: Matrix Chain Multiplication, Burst Balloons, Predict the Winner.

Is there a brute force solution for The Score of Students Solving Math Expression?

Yes. Brute force (try every split recursively) takes O(Catalan(n) · V²) time and O(n · V) space. Compute the correct value with normal precedence.

Which edge cases should I test for The Score of Students Solving Math Expression?

Only one kind of operator: every grouping gives the same value, so no answer earns 2 points; A 0 that wipes out a huge intermediate product; An answer equal to the correct value must get 5, never 2 (the correct value is also a reachable grouping); Intermediate results above 1000 can be dropped: no answer is that large and values never shrink except by 0, which yields 0 anyway.