The Score of Students Solving Math Expression

Hard

Flipkart

1 view

Topics:

ArraysStringsDynamic Programming

You are given a string s that contains digits 0-9, addition symbols '+', and multiplication symbols '*' only, representing a valid math expression of single digit numbers (e.g., 3+5*2). This expression was given to n elementary school students. The students were instructed to get the answer of the expression by following this order of operations:

Compute multiplication, reading from left to right; Then,
Compute addition, reading from left to right.

You are given an integer array answers of length n, which are the submitted answers of the students in no particular order. You are asked to grade the answers, by following these rules:

If an answer equals the correct answer of the expression, this student will be rewarded 5 points;
Otherwise, if the answer could be interpreted as if the student applied the operators in the wrong order but had correct arithmetic, this student will be rewarded 2 points;
Otherwise, this student will be rewarded 0 points.

Return the sum of the points of the students.

Example 1:

Input: s = "7+3*1*2", answers = [20,13,42]
Output: 7
Explanation: As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,13,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [20,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.

Example 2:

Input: s = "3+5*2", answers = [13,0,10,13,13,16,16]
Output: 19
Explanation: The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [13,0,10,13,13,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,16,16]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.

Example 3:

Input: s = "6+0*1", answers = [12,9,6,4,8,6]
Output: 10
Explanation: The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.

Constraints:

3 <= s.length <= 31
s represents a valid expression that contains only digits 0-9, '+', and '*' only.
All the integer operands in the expression are in the inclusive range [0, 9].
1 <= The count of all operators ('+' and '*') in the math expression <= 15
Test data are generated such that the correct answer of the expression is in the range of [0, 1000].
Test data are generated such that value never exceeds 10⁹ in intermediate steps of multiplication.
n == answers.length
1 <= n <= 10⁴
0 <= answers[i] <= 1000

Try coding it in LeetCode

The Score of Students Solving Math Expression

Hard

Flipkart

1 view

Topics:

ArraysStringsDynamic Programming

You are given a string s that contains digits 0-9, addition symbols '+', and multiplication symbols '*' only, representing a valid math expression of single digit numbers (e.g., 3+5*2). This expression was given to n elementary school students. The students were instructed to get the answer of the expression by following this order of operations:

Compute multiplication, reading from left to right; Then,
Compute addition, reading from left to right.

You are given an integer array answers of length n, which are the submitted answers of the students in no particular order. You are asked to grade the answers, by following these rules:

If an answer equals the correct answer of the expression, this student will be rewarded 5 points;
Otherwise, if the answer could be interpreted as if the student applied the operators in the wrong order but had correct arithmetic, this student will be rewarded 2 points;
Otherwise, this student will be rewarded 0 points.

Return the sum of the points of the students.

Example 1:

Input: s = "7+3*1*2", answers = [20,13,42]
Output: 7
Explanation: As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,13,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [20,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.

Example 2:

Input: s = "3+5*2", answers = [13,0,10,13,13,16,16]
Output: 19
Explanation: The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [13,0,10,13,13,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,16,16]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.

Example 3:

Input: s = "6+0*1", answers = [12,9,6,4,8,6]
Output: 10
Explanation: The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.

Constraints:

3 <= s.length <= 31
s represents a valid expression that contains only digits 0-9, '+', and '*' only.
All the integer operands in the expression are in the inclusive range [0, 9].
1 <= The count of all operators ('+' and '*') in the math expression <= 15
Test data are generated such that the correct answer of the expression is in the range of [0, 1000].
Test data are generated such that value never exceeds 10⁹ in intermediate steps of multiplication.
n == answers.length
1 <= n <= 10⁴
0 <= answers[i] <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the expression string and the values of the digits within it?
Can the student answers contain duplicate values, and how should duplicate correct/alternative answers be handled when calculating the score?
Is the expression guaranteed to be syntactically valid, and if so, can I assume operator precedence is always followed (multiplication before addition)?
Are there any constraints on the number of '+', and '*' operators in the expression?
If no student answers match the correct answer or any alternative parenthesizations, what should the function return (e.g., 0, null, throw an exception)?

Brute Force Solution

Approach

The brute force approach to this problem is like trying every single possible way to calculate the math expression. We explore all combinations of operations, regardless of order, and then compare the results to the student's answer to calculate a score.

Here's how the algorithm would work step-by-step:

First, we need to list out every possible way to do the math in the expression. Think of it like trying out every combination of adding and multiplying, ignoring the usual order of operations.
For each of these possible ways of doing the math, we calculate the final result.
Now, compare each of these results to the student's answer. If a result matches the student's answer, that's great!
If the student's answer is correct (matches the actual correct answer), they get a certain number of points.
If the student's answer is wrong but matches one of our other possible calculations, they get a different, smaller number of points.
If the student's answer doesn't match any of our possible calculations, they get no points.
Sum up the points based on these comparisons to find the student's final score.

Code Implementation

def score_of_students(expression, correct_answer, student_answer):
    possible_results = set()
    numbers = []
    operators = []
    number_string = ''

    for character in expression:
        if character.isdigit():
            number_string += character
        else:
            numbers.append(int(number_string))
            number_string = ''
            operators.append(character)

    numbers.append(int(number_string))

    def calculate_possible_results(current_numbers, current_operators, current_result):
        if not current_operators:
            possible_results.add(current_result)
            return

        for i in range(len(current_operators)):
            next_numbers = current_numbers[:]
            next_operators = current_operators[:]
            first_number = next_numbers.pop(i)
            second_number = next_numbers.pop(i)
            operator = next_operators.pop(i)

            if operator == '+':
                new_result = first_number + second_number
            else:
                new_result = first_number * second_number

            if new_result <= 1000:
                calculate_possible_results(next_numbers[:i] + [new_result] + next_numbers[i:], next_operators, current_result)

    calculate_possible_results(numbers, operators, 0)

    # Calculate the correct answer using eval.
    actual_result = eval(expression)

    if student_answer == actual_result:
        return 5

    # Check if the student's answer is among possible wrong answers.
    if student_answer in possible_results:
        return 2

    return 0

Big(O) Analysis

Time Complexity

O(4^n) – The brute force approach explores all possible calculation orders in the expression. With n numbers, there are n-1 operations. For each operation, we effectively have two choices (multiply or add) leading to 2^(n-1) potential calculation orders. Since each calculation order can involve roughly 2^(n-1) operations to perform additions and multiplications, and since the number of possible answers can grow exponentially, the time complexity is roughly O(2^(n-1) * 2^(n-1)), which can be approximated to O(4^n) after considering constant factors and simplifications in the Big O notation for worst-case performance. The number of possible orderings/paranthesizations grow with Catalan numbers, which are bounded by 4^n.

Space Complexity

O(N^2) – The brute force approach involves generating all possible evaluation results of the math expression. To store these intermediate and final results, a data structure like a set or a dynamic programming table is required. The number of possible results can grow proportionally to N^2, where N is the number of operands and operators in the expression. Therefore, the auxiliary space used to store these results is O(N^2). Other variables have constant space complexity.

Optimal Solution

Approach

To efficiently determine the possible scores, we use a strategy where we build up all possible correct and incorrect answers from smaller sub-expressions. This avoids exhaustively checking every possible calculation order.

Here's how the algorithm would work step-by-step:

First, figure out the correct answer to the math expression using the normal order of operations.
Then, recognize that there are a limited number of possible results students can get by evaluating the expression in different orders.
Create a way to store the possible results for each sub-expression, that is, parts of the main expression.
Start with the smallest sub-expressions (like individual numbers) and then combine them to form larger sub-expressions.
For each sub-expression, try every possible order of calculation using the results of its smaller parts.
Keep track of all the unique values you get from these different orders of calculation.
Finally, compare the unique values to the students' answers and add up the points (5 for correct, 2 for possible).
By breaking the problem down into smaller pieces and building up, you can find all possible results without trying every single combination from scratch.

Code Implementation

def score_of_students(math_expression, student_answers):
    tokens = []
    number = 0
    for character in math_expression:
        if character.isdigit():
            number = number * 10 + int(character)
        else:
            tokens.append(number)
            tokens.append(character)
            number = 0
    tokens.append(number)

    def calculate_correct_answer(expression_tokens):
        operands = []
        operators = []
        
        for token in expression_tokens:
            if isinstance(token, int):
                operands.append(token)
            else:
                while operators and operators[-1] == '*' and token != '*':
                    operator = operators.pop()
                    operand2 = operands.pop()
                    operand1 = operands.pop()
                    operands.append(operand1 * operand2)
                operators.append(token)

        while operators:
            operator = operators.pop()
            operand2 = operands.pop()
            operand1 = operands.pop()
            if operator == '+':
                operands.append(operand1 + operand2)
            else:
                operands.append(operand1 * operand2)
        
        return operands[0]

    correct_answer = calculate_correct_answer(tokens)

    # DP table to store possible results for each sub-expression
    possible_results = {}

    def calculate_possible_results(start, end):
        if (start, end) in possible_results:
            return possible_results[(start, end)]

        if start == end:
            possible_results[(start, end)] = {tokens[start]}
            return possible_results[(start, end)]

        results = set()
        # Iterate through all possible split points
        for i in range(start + 1, end, 2):
            operator = tokens[i]
            # Compute possible results for left and right sub-expressions
            left_results = calculate_possible_results(start, i - 1)
            right_results = calculate_possible_results(i + 1, end)

            # Combine results using the operator
            for left_result in left_results:
                for right_result in right_results:
                    if operator == '+':
                        result = left_result + right_result
                    else:
                        result = left_result * right_result
                    if 0 <= result <= 1000:
                        results.add(result)

        possible_results[(start, end)] = results
        return results

    all_possible_answers = calculate_possible_results(0, len(tokens) - 1)

    total_score = 0
    for answer in student_answers:
        if answer == correct_answer:
            total_score += 5
        elif answer in all_possible_answers:
            total_score += 2

    # Return the calculated score.
    return total_score

Big(O) Analysis

Time Complexity

O(n^3) – The solution uses dynamic programming to compute all possible results of sub-expressions. The outermost loops iterate through all possible sub-expressions, which takes O(n^2) time where n is the length of the expression. For each sub-expression, we iterate through all possible splitting points to combine the results of smaller sub-expressions. This inner loop takes O(n) time. Therefore, the overall time complexity is O(n^2 * n) = O(n^3).

Space Complexity

O(N^2 * M) – The algorithm stores possible results for each sub-expression within a range. Since there are O(N^2) possible sub-expressions (where N is the length of the expression), and for each sub-expression we store a set of possible results, the space complexity depends on the maximum possible value of any intermediate result (M). Therefore, we have a table of size O(N^2) where each entry can store up to M unique values. The space required to store these unique values for each subexpression results in O(N^2 * M) space. N represents the length of the expression string, and M is related to the maximum possible intermediate score.

Edge Cases

Case	How to Handle
Empty expression string	Return 0 since no correct answer can be computed and no student answers are valid.
Null expression string or null student answers list	Throw an IllegalArgumentException or return 0 after checking for null inputs.
Expression string contains invalid characters other than digits, '+', and '*'	Throw an IllegalArgumentException after validating all characters in the input string.
Very long expression string leading to integer overflow	Use dynamic programming with memoization to avoid recomputation and handle potential overflows during intermediate calculations (values are bounded to 1000).
Expression with consecutive operators ('++' or '*' or '+')	Throw an IllegalArgumentException after validating that no consecutive operators exist.
Student answers list contains duplicate answers	The scoring logic should handle duplicates by incrementing the score accordingly for each duplicate answer.
Student answers containing values outside the 0-1000 range, although intermediate calculations should always be in range	The condition `0 <= value <= 1000` is crucial during the calculation of possible parenthesizations, so we only consider student answers falling within the range 0-1000 when checking student answers for being an alternative parenthesization.
Expression that results in a correct answer outside the range [0, 1000]	The problem statement specifies that incorrect alternative parenthesizations must result in values within the specified range, but the correct value could exceed it; compute it as part of alternative parenthesization but ignore for awarding 5 points.