We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Score of Students Solving Math Expression

Number: 2147

Difficulty: Hard

Paid? No

Companies: Flipkart

Problem Description

Given a string s that represents a valid math expression containing only single digit numbers and the operators '+' and '*', compute the correct answer by first performing all multiplications from left to right and then performing additions from left to right. In addition, determine all possible results that could be obtained if a student mistakenly evaluated the expression by applying the operations in a different order (i.e. by placing parentheses in any valid way). You are given an array of submitted answers. For each answer, if it equals the correct result, award 5 points; otherwise, if it matches one of the alternative possible results (but is not equal to the correct answer), award 2 points; otherwise, award 0 points. Return the total points accumulated.

Key Insights

  • The correct answer is computed by simulating the given unusual order: perform multiplication (left-to-right) before doing addition (left-to-right).
  • Using dynamic programming (or recursion with memoization) allows us to compute every possible result of the expression by considering every possible parenthesization.
  • Use a set to store unique alternative results to avoid duplicate awarding when the same value can be computed in multiple ways.
  • If an alternative evaluation produces the same result as the correct evaluation, then only 5 points should be awarded for that answer.

Space and Time Complexity

Time Complexity: O(n^3) in the worst case where n (the count of numbers) is small (at most 16), due to exploring all possible splits. Space Complexity: O(n^2) to store the intermediate results in the dynamic programming memoization table.

Solution

We first parse the expression into a list of numbers and a list of operators. To compute the correct answer, we simulate the specified order of operations: first process all multiplications from left to right, and then perform consecutive additions.

Then, we use a dynamic programming approach to compute all possible results by considering every valid way to parenthesize the expression. Specifically, for a subexpression spanning indices i to j (representing numbers), we recursively divide at every operator position and combine the left and right results based on the operator between them.

Once we have the correct result and the set of all possible evaluation outcomes from any parenthesization, we iterate through the submitted answers. For each answer, if it equals the correct result, we add 5 points; if not and it is found in the possible outcomes (excluding the correct result), we add 2 points; otherwise, we add 0 points.

Data structures used include:

  • Lists to hold the separated numbers and operators.
  • A memoization dictionary (or table) for the dynamic programming approach.
  • A set to store unique evaluation outcomes from the recursive computations.

Code Solutions

# Python solution with detailed comments

def scoreOfStudents(s, answers):
    # Parse the expression into numbers and operators.
    numbers, operators = [], []
    i, n = 0, len(s)
    while i < n:
        if s[i].isdigit():
            numbers.append(int(s[i]))
        else:
            operators.append(s[i])
        i += 1

    # Compute the correct answer using the special evaluation order:
    # first do all multiplication (left to right) then addition (left to right)
    def compute_correct(numbers, operators):
        # First perform multiplication in one pass
        mult_result = []
        mult_result.append(numbers[0])
        for idx, op in enumerate(operators):
            if op == '*':
                mult_result[-1] = mult_result[-1] * numbers[idx+1]
            else:  # op == '+'
                mult_result.append(numbers[idx+1])
        # Now compute addition (left to right)
        result = mult_result[0]
        for num in mult_result[1:]:
            result += num
        return result

    correct_val = compute_correct(numbers, operators)

    # Use dynamic programming (memoization) to compute all possible results
    from functools import lru_cache
    total_numbers = len(numbers)
    
    # dp(i, j) returns a set of values from evaluating the sub-expression numbers[i:j+1]
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == j:
            return {numbers[i]}
        ans_set = set()
        # splitting at every operator between i and j
        for k in range(i, j):
            left_results = dp(i, k)
            right_results = dp(k+1, j)
            op = operators[k]  # operator between the result of left side and right side
            for left in left_results:
                for right in right_results:
                    if op == '+':
                        ans_set.add(left + right)
                    elif op == '*':
                        ans_set.add(left * right)
        return ans_set

    possible_results = dp(0, total_numbers - 1)

    total_score = 0
    # Check each student's answer and assign points accordingly
    for answer in answers:
        if answer == correct_val:
            total_score += 5
        elif answer in possible_results:
            total_score += 2
    return total_score

# Example usage:
# s = "7+3*1*2"
# answers = [20, 13, 42]
# print(scoreOfStudents(s, answers))  # Expected output: 7
← Back to All Questions