#2019
The Score of Students Solving Math Expression
HardArrayHash TableMathStringDynamic ProgrammingStackMemoizationHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal approach evaluates the expression using the correct order of operations directly and calculates the wrong order by changing the precedence of operations. This avoids unnecessary recomputation and significantly reduces complexity.
⚙️
Algorithm
4 steps- 1Step 1: Parse the string to extract numbers and operators.
- 2Step 2: Compute the correct result by applying multiplication first, then addition.
- 3Step 3: Compute the wrong result by applying addition first, then multiplication.
- 4Step 4: Compare both results with the students' answers to assign points.
solution.py20 lines
1def score_students(s, answers):
2 numbers = [int(x) for x in s.replace('+', ' ').replace('*', ' ').split()]
3 operators = [c for c in s if c in '+*']
4 correct_answer = 0
5 temp = numbers[0]
6 for i in range(len(operators)):
7 if operators[i] == '*':
8 temp *= numbers[i + 1]
9 else:
10 correct_answer += temp
11 temp = numbers[i + 1]
12 correct_answer += temp
13 wrong_answer = (sum(numbers) * numbers[0]) if len(numbers) > 1 else numbers[0]
14 points = 0
15 for answer in answers:
16 if answer == correct_answer:
17 points += 5
18 elif answer == wrong_answer:
19 points += 2
20 return pointsℹ
Complexity note: The time complexity is O(n) because we only traverse the string a couple of times to parse numbers and operators, and then compute the results in a single pass.
- 1Understanding operator precedence is crucial.
- 2Evaluating expressions in different orders can yield different results.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.