2019. The Score of Students Solving Math Expression

HardStackMemoizationArrayMathStringDynamic Programming
Leetcode Link

Problem Description

In this problem, a valid mathematical expression consisting solely of single-digit numbers, addition (+), and multiplication (*) symbols is given. An example of such an expression is 3+5*2. The expression is to be evaluated by a group of elementary school students, and their answers are to be graded based on certain rules. The order of operations specified for the students is:

  1. Evaluate multiplication from left to right.
  2. Then, evaluate addition from left to right.

The students' submitted answers are in the integer array answers. The task is to grade these answers using the following rules:

  • If an answer is correct, the student earns 5 points.
  • If an answer is incorrect but could result from a wrong operators’ order while still using correct arithmetic, the student receives 2 points.
  • For all other cases, the student receives 0 points.

The goal is to calculate the total points scored by all students.

Intuition

The solution approach is divided into several steps:

  1. Correct Answer Calculation:

    • We first need to evaluate the given expression according to the specified order of operations. This is done by a function which processes multiplication first and then addition, all done from left to right.

  2. All Possible Answers Generation:

    • Create and populate a set of all possible answers obtained by applying multiplication and addition operations in any order within the constraints, using dynamic programming. This set includes all the values that can be achieved by any permutation of the operations keeping the single-digit numbers in order, and considering that any intermediate or final result doesn't exceed 1000.

  3. Grading the Student Answers:

    • Cross-reference each student's answer against the correct answer and the set of possible answers. Based on the comparison, assign the appropriate points as per the rules and calculate the total score.

The final solution is the sum of all points the students earned for their answers.

Learn more about Stack, Memoization, Math and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the most two important steps in writing a depth first search function? (Select 2)

Solution Approach

The implementation of the solution involves a couple of distinct phases; calculation of the correct answer, generation of all possible answers, and grading of the student submissions:

  1. Calculate the Correct Answer: The cal function traverses the given string s, computing the result following the rules mentioned (multiplication before addition). It uses a "precedence" approach, keeping track of the current result and the last seen number. As it iterates:

    • If it encounters a *, it multiplies the last seen number (pre) by the next number.
    • If it encounters a +, it adds pre to the cumulative result (res) and resets pre to the next number. After the traversal, addition of the last number to res gives us the correct answer.

  2. Generate All Possible Answers:

    • A 2D array f consists of sets that track all possible results you can get from subexpressions within the input string s. The array f[i][j] includes all unique results you can get using numbers and operators between the i-th and j-th single-digit numbers, with all permutations of the operations.
    • To generate this list efficiently, we use dynamic programming. We consider longer subexpressions based on the results of shorter subexpressions we've already computed. For every pair of (i, j), we try all possible split points k between them to calculate the results of f[i][k] and f[k + 1][j], and combine them with both addition and multiplication.
    • All the intermediate results are constrained by the rule that they must be less than or equal to 1000 to reduce complexity.

  3. Grading the Student Answers:

    • We use Python's Counter from the collections module to track how many times each answer appears in the answers list.
    • A loop checks each unique student answer:
      • Answers matching the correct answer (x) are multiplied by 5 for their score contribution.
      • Answers that don't match x but are found within our generated set f[0][m - 1] (all possible answers from the expression) are multiplied by 2.
    • The ans variable accumulates the total score from all graded answers and is returned as the final result.

This comprehensive approach ensures that we evaluate the correct answer once, compute all possible answers once, and then compare each student's answer efficiently without repetitive computation. Data structures like arrays and sets are crucial here, with sets providing a fast look-up for checking the possible answers, and arrays allowing an organized method to iterate through the expression and answers.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Given Expression: 2+3*2

  1. Calculate the Correct Answer:

    • We start by processing multiplication before addition from left to right.
    • There's only one multiplication here: 3*2, which equals 6.
    • The entire expression becomes 2+6, and after the addition, we have 8.
    • So, the correct answer is 8.

  2. Generate All Possible Answers:

    • Now consider all possible answers based on permutations of operations.
    • If we ignore the precedence and calculate from left to right, we would get (2+3)+2 which is 7.
    • If we consider any permutation, these are the only two possible outcomes because only one multiplication is present, and it always occurs between the last two numbers.
    • So our set of all possible answers is {8, 7}.

  3. Grading the Student Answers:

    • Imagine the students submitted the following answers: [8, 7, 5].
    • We check each answer:
      • 8 is correct, so it gets 5 points.
      • 7 is incorrect but is in the set of possible answers, so it gets 2 points.
      • 5 is neither correct nor in the set of possible answers, so it gets 0 points.
    • Total points are 5 (for 8) + 2 (for 7) + 0 (for 5) = 7.

Now imagine a function where this logic is implemented, where it checks each submitted answer against the correct answer and the set of all possible answers to build up the total score according to the grading rules. This walkthrough enforces the understanding of the evaluation and grading process based on the defined rules and demonstrates how the solution approach is applied to an example.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
5        # Inner function to calculate the correct result following the rules of arithmetic
6        def calculate_correct_result(expression: str) -> int:
7            result, previous_operand = 0, int(expression[0])
8            for i in range(1, n, 2):
9                if expression[i] == "*":
10                    previous_operand *= int(expression[i + 1])
11                else:
12                    result += previous_operand
13                    previous_operand = int(expression[i + 1])
14            result += previous_operand
15            return result
16
17        n = len(s)
18        correct_result = calculate_correct_result(s)
19        num_operands = (n + 1) >> 1  # Number of operands in the expression
20        possible_results = [[set() for _ in range(num_operands)] for _ in range(num_operands)]
21      
22        # Initialize sets with individual numbers in the expression
23        for i in range(num_operands):
24            possible_results[i][i] = {int(s[i << 1])}
25      
26        # Compute all possible results using dynamic programming
27        for i in range(num_operands - 1, -1, -1):
28            for j in range(i, num_operands):
29                for k in range(i, j):
30                    for left_operand in possible_results[i][k]:
31                        for right_operand in possible_results[k + 1][j]:
32                            operator = s[k << 1 | 1]
33                            if operator == "+" and left_operand + right_operand <= 1000:
34                                possible_results[i][j].add(left_operand + right_operand)
35                            elif operator == "*" and left_operand * right_operand <= 1000:
36                                possible_results[i][j].add(left_operand * right_operand)
37      
38        # Count the occurrences of each answer
39        answer_count = Counter(answers)
40      
41        # Start with the score for correct answers (5 points each)
42        total_score = answer_count[correct_result] * 5
43      
44        # Add scores for partially correct answers (2 points each)
45        for answer, count in answer_count.items():
46            if answer != correct_result and answer in possible_results[0][num_operands - 1]:
47                total_score += count * 2
48      
49        return total_score
50
1class Solution {
2    // Main function to calculate the score of students' answers.
3    public int scoreOfStudents(String s, int[] answers) {
4        int length = s.length();
5        int correctAnswer = calculateCorrectAnswer(s);
6        int numExpressions = (length + 1) >> 1; // Half the length of the string, representing the number of expressions (1 + 2 becomes 2 expressions - '1' and '2')
7        Set<Integer>[][] possibleResults = new Set[numExpressions][numExpressions];
8      
9        // Initialize the sets.
10        for (int i = 0; i < numExpressions; ++i) {
11            for (int j = 0; j < numExpressions; ++j) {
12                possibleResults[i][j] = new HashSet<>();
13            }
14            // Single digits are valid possible results.
15            possibleResults[i][i].add(s.charAt(i << 1) - '0');
16        }
17      
18        // Build all possible results using dynamic programming.
19        for (int i = numExpressions - 1; i >= 0; --i) {
20            for (int j = i; j < numExpressions; ++j) {
21                for (int k = i; k < j; ++k) {
22                    for (int left : possibleResults[i][k]) {
23                        for (int right : possibleResults[k + 1][j]) {
24                            char operation = s.charAt(k << 1 | 1);
25                            if (operation == '+' && left + right <= 1000) {
26                                possibleResults[i][j].add(left + right);
27                            } else if (operation == '*' && left * right <= 1000) {
28                                possibleResults[i][j].add(left * right);
29                            }
30                        }
31                    }
32                }
33            }
34        }
35      
36        int[] counts = new int[1001];
37        for (int answer : answers) {
38            counts[answer]++;
39        }
40      
41        // Award points for the correct answer.
42        int totalScore = 5 * counts[correctAnswer];
43      
44        // Award points for possible but incorrect results.
45        for (int i = 0; i <= 1000; ++i) {
46            if (i != correctAnswer && possibleResults[0][numExpressions - 1].contains(i)) {
47                totalScore += 2 * counts[i];
48            }
49        }
50      
51        return totalScore;
52    }
53
54    // Helper method to calculate the correct answer of the expression.
55    private int calculateCorrectAnswer(String s) {
56        int result = 0, prevNumber = s.charAt(0) - '0';
57        for (int i = 1; i < s.length(); i += 2) {
58            char operation = s.charAt(i);
59            int currNumber = s.charAt(i + 1) - '0';
60            if (operation == '*') {
61                prevNumber *= currNumber;
62            } else {
63                result += prevNumber;
64                prevNumber = currNumber;
65            }
66        }
67        result += prevNumber;
68        return result;
69    }
70}
71
1#include <string>
2#include <vector>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8    // Calculates the score for students' answers to a math expression quiz
9    int scoreOfStudents(string s, vector<int>& answers) {
10        int expressionSize = s.size();
11      
12        // `correctAnswer` is the correct answer calculated from the expression
13        int correctAnswer = calculateCorrectAnswer(s);
14      
15        // Convert from expression length to number of operands
16        int operandCount = (expressionSize + 1) >> 1;
17      
18        // Dynamic programming table: f[i][j] stores possible results of subexpression from i to j
19        unordered_set<int> dpTable[operandCount][operandCount];
20      
21        for (int i = 0; i < operandCount; ++i) {
22            // Initialize the set with single operand values
23            dpTable[i][i] = {s[i * 2] - '0'};
24        }
25      
26        // Fill the DP table in a bottom-up manner
27        for (int i = operandCount - 1; i >= 0; --i) {
28            for (int j = i; j < operandCount; ++j) {
29                for (int k = i; k < j; ++k) {
30                    // Calculate all possible results by combining 
31                    // results from dpTable[i][k] and dpTable[k+1][j] with the operator in between
32                    for (int leftOperand : dpTable[i][k]) {
33                        for (int rightOperand : dpTable[k + 1][j]) {
34                            char op = s[k * 2 + 1];
35                            // If operation is '+' and result is within limits, add to set
36                            if (op == '+' && leftOperand + rightOperand <= 1000) {
37                                dpTable[i][j].insert(leftOperand + rightOperand);
38                            }
39                            // If operation is '*' and result is within limits, add to set
40                            else if (op == '*' && leftOperand * rightOperand <= 1000) {
41                                dpTable[i][j].insert(leftOperand * rightOperand);
42                            }
43                        }
44                    }
45                }
46            }
47        }
48      
49        // Answer counting array
50        int answerCounts[1001] = {};
51        for (int studentAnswer : answers) {
52            ++answerCounts[studentAnswer];
53        }
54      
55        // Calculate score based on the correct answer
56        int score = 5 * answerCounts[correctAnswer];
57      
58        // Award points for possible but incorrect answers within constraints
59        for (int i = 0; i <= 1000; ++i) {
60            if (i != correctAnswer && dpTable[0][operandCount - 1].count(i)) {
61                score += answerCounts[i] * 2;
62            }
63        }
64      
65        return score;
66    }
67
68private:
69    // Helper function to calculate the correct answer from the expression
70    int calculateCorrectAnswer(string& s) {
71        int result = 0; // Stores the final expression result
72        int currentValue = s[0] - '0'; // Temporary to hold the current 'term' in the expression
73      
74        for (int i = 1; i < s.size(); i += 2) {
75            int nextValue = s[i + 1] - '0';
76            // Apply the operation to the current and next values
77            if (s[i] == '*') {
78                currentValue *= nextValue; // Multiplication
79            } else {
80                result += currentValue; // Addition
81                currentValue = nextValue; // Assign next value to the current
82            }
83        }
84        result += currentValue; // Add the last term to the result
85      
86        return result;
87    }
88};
89
1// Function to compute and return the score given student's answers
2function scoreOfStudents(solution: string, answers: number[]): number {
3    // Determine the length of the solution expression
4    const solutionLength = solution.length;
5
6    // Helper function to calculate the correct answer using standard math rules
7    const calculate = (expression: string): number => {
8        let result = 0;
9        let previousOperand = expression.charCodeAt(0) - '0'.charCodeAt(0);
10        for (let i = 1; i < expression.length; i += 2) {
11            const currentOperand = expression.charCodeAt(i + 1) - '0'.charCodeAt(0);
12            if (expression[i] === '+') {
13                result += previousOperand;
14                previousOperand = currentOperand;
15            } else {
16                previousOperand *= currentOperand;
17            }
18        }
19        result += previousOperand;
20        return result;
21    };
22
23    // Calculate the correct answer of the expression
24    const correctAnswer = calculate(solution);
25
26    // The number of operands in the expression
27    const operandsCount = (solutionLength + 1) >> 1;
28
29    // Set up a 2D array for dynamic programming; each element is a set containing possible results
30    const possibleResults: Set<number>[][] = Array.from({ length: operandsCount }, () =>
31        Array.from({ length: operandsCount }, () => new Set<number>())
32    );
33
34    // Initialize the diagonal of the DP matrix with the operands of the expression
35    for (let i = 0; i < operandsCount; ++i) {
36        possibleResults[i][i].add(parseInt(solution[i << 1]));
37    }
38
39    // Calculate all possible results for every sub-expression
40    for (let i = operandsCount - 1; i >= 0; --i) {
41        for (let j = i; j < operandsCount; ++j) {
42            for (let k = i; k < j; ++k) {
43                for (const left of possibleResults[i][k]) {
44                    for (const right of possibleResults[k + 1][j]) {
45                        const operator = solution[(k << 1) + 1];
46                        if (operator === '+' && left + right <= 1000) {
47                            possibleResults[i][j].add(left + right);
48                        } else if (operator === '*' && left * right <= 1000) {
49                            possibleResults[i][j].add(left * right);
50                        }
51                    }
52                }
53            }
54        }
55    }
56
57    // Initialize a count array to count the frequency of each answer
58    const answerCount: number[] = Array(1001).fill(0);
59    answers.forEach((answer) => {
60        answerCount[answer]++;
61    });
62
63    // Calculate the score by giving 5 points for the correct answer
64    let totalScore = answerCount[correctAnswer] * 5;
65
66    // Add 2 points for each possible answer (exclude the correct answer) included in the dynamic programming matrix 
67    for (let i = 0; i <= 1000; ++i) {
68        if (i !== correctAnswer && possibleResults[0][operandsCount - 1].has(i)) {
69            totalScore += answerCount[i] * 2;
70        }
71    }
72
73    // Return the total score
74    return totalScore;
75}
76
Not Sure What to Study? Take the 2-min Quiz：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

Time Complexity

The time complexity of the method scoreOfStudents is determined by several nested loops and operations on sets.

  • The first part of the scoreOfStudents method involves a single pass calculation through string s to compute the correct answer with standard arithmetic, which has a time complexity of O(n), where n is the length of the input string s.

  • The second part initializes the 2D array f with empty sets, which takes O(m^2) time, where m = (n + 1) >> 1 represents the number of operands in the string s.

  • The third part involves filling the 2D array f, where for each (i, j) pair, there are up to j - i splits (controlled by k) and up to 1000 (the cap for l + r or l * r) operations for merging the results. In the worst case, this could mean iterating up to 1000 * (j - i) times for each k. Since j - i can range up to m, the worst-case time complexity for this section is O(m^3 * 1000).

  • The final part of the method goes through all unique answers provided by students and checks whether these answers are in f[0][m - 1], assigning points accordingly. If there are a distinct answers, with each answer requiring O(1) time to check membership in the set and assigning points, the time complexity for this part is O(a).

Combining all parts, the overall time complexity is O(n) + O(m^2) + O(m^3 * 1000) + O(a). Since m is roughly n/2, this simplifies to O(n^3) as the dominant term, taking into account that m^3 essentially becomes (n/2)^3.

Space Complexity

The space complexity of the method scoreOfStudents primarily depends on the storage for the 2D array f and the Counter for answers cnt.

  • The 2D array f has m * m cells, each potentially storing a set of integers with a maximum size of 1000. Thus, the worst-case space complexity is O(m^2 * 1000). Since m is roughly n/2, this is equivalent to O(n^2).

  • The Counter for answers cnt will contain at most a pairs, where a is the number of unique answers. Therefore, its space complexity is O(a).

The overall space complexity is the sum of the space required by f and cnt, which is O(n^2) + O(a). Since n^2 is typically larger than a, the dominant term is O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫