Expression Add Operators

📋

Problem

Imagine you are building a calculator app that can insert operators between digits to reach a target value. How do you find all valid expressions that evaluate exactly to that target?

Given a string num that contains only digits and an integer target, return all possibilities to add binary operators ('+', '-', or '*') between the digits so that the resultant expression evaluates to the target value. The returned expressions should not contain any spaces and must not have leading zeros in any operand except for the number zero itself.

1 ≤ num.length ≤ 10num consists of only digits.-2^31 ≤ target ≤ 2^31 - 1

Edge cases: num = "000", target = 0 → ["0+0+0", "0+0-0", "0+0*0", "0-0+0", "0-0-0", "0-0*0", "0*0+0", "0*0-0", "0*0*0"]num = "105", target = 5 → ["1*0+5", "10-5"] (leading zero in '05' is invalid)num = "3456237490", target = 9191 → [] (no valid expressions)

</>

IDE

def addOperators(num: str, target: int) -> list:public List<String> addOperators(String num, int target)vector<string> addOperators(string num, int target)function addOperators(num, target)

def addOperators(num: str, target: int) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> addOperators(String num, int target) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> addOperators(string num, int target) {
    // Write your solution here
    return {};
}

function addOperators(num, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1+2+3Missing multiplication operator expressions due to ignoring multiplication precedence.✅ Track last operand and adjust evaluated value when '*' operator is used: evaluated = evaluated - last_operand + last_operand * current.

Wrong: 1*0+510-51*05Allowing operands with leading zeros like '05' which are invalid.✅ Add check to skip operands starting with '0' if length > 1.

Wrong: 0+0+00+0-00-0+00-0-00*0*000+0Allowing multi-digit operands with leading zeros like '00'.✅ Only allow single '0' as operand; skip multi-digit operands starting with '0'.

Wrong: 2+2+22+2+22+2+22*2*22*2*22*2*2Reusing digits or generating duplicate expressions due to incorrect index advancement.✅ Advance index correctly in recursion to use each digit exactly once and avoid duplicates.

Wrong: Solution times out on large inputs due to exponential complexity.✅ Implement pruning and efficient string building to reduce runtime.

✓

Test Cases

Focus on handling base cases like empty input and single digits correctly.

Ensure correct operator precedence and operand validation to avoid subtle bugs.

Optimize your backtracking with pruning and efficient string operations.

t1_01basic

Input{"num":"123","target":6}

Expected["1+2+3","1*2*3"]

⏱ Performance - must finish in 2000ms

Both expressions evaluate to 6: 1+2+3=6 and 1*2*3=6.

💡 Try building expressions by inserting operators between digits.

💡 Use backtracking to explore all operator combinations and evaluate expressions.

💡 Track the current evaluated value and last operand to handle multiplication correctly.

Why it failed: Incorrect or missing expressions for target 6. Likely missing multiplication handling or incorrect evaluation logic. Fix by tracking last operand and adjusting evaluated value when '*' operator is used.

✓ Correctly generates all expressions evaluating to target 6.

t1_02basic

Input{"num":"232","target":8}

Expected["2*3+2","2+3*2"]

⏱ Performance - must finish in 2000ms

Expressions '2*3+2' and '2+3*2' both evaluate to 8.

💡 Consider operator precedence when evaluating expressions.

💡 Use backtracking with tracking of last operand to correctly handle multiplication.

💡 Avoid leading zeros in operands except for zero itself.

Why it failed: Missing valid expressions or incorrect evaluation for target 8. Possibly ignoring operator precedence or leading zero rules. Fix by implementing correct multiplication undo logic and skipping operands with leading zeros.

✓ Correctly finds all valid expressions evaluating to 8.

t2_01edge

Input{"num":"","target":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input string yields no expressions.

💡 Check how your code handles empty input strings.

💡 Ensure base case returns empty list when no digits are available.

💡 Return empty list immediately if input string is empty.

Why it failed: Code crashes or returns non-empty list on empty input. Fix by adding base case to return empty list if num is empty.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"num":"1","target":1}

Expected["1"]

⏱ Performance - must finish in 2000ms

Single digit equal to target returns single expression without operators.

💡 Handle single digit input as a base case.

💡 Return the digit itself if it equals the target.

💡 Avoid adding operators when only one digit is present.

Why it failed: Fails to return single digit expression when num length is 1. Fix by checking if entire num equals target and returning it as a valid expression.

✓ Correctly returns single digit expression matching target.

t2_03edge

Input{"num":"000","target":0}

Expected["0+0+0","0+0-0","0+0*0","0-0+0","0-0-0","0-0*0","0*0+0","0*0-0","0*0*0"]

⏱ Performance - must finish in 2000ms

All combinations of operators between zeros evaluate to 0; leading zeros allowed only for zero itself.

💡 Handle operands with zero carefully to avoid invalid leading zeros.

💡 Allow '0' as a valid operand but disallow '00', '000', etc.

💡 Generate all operator combinations between zeros and verify evaluation.

Why it failed: Incorrectly skipping valid zero operands or generating invalid leading zero operands. Fix by allowing single '0' operands and skipping multi-digit operands starting with '0'.

✓ Correctly generates all valid expressions with zeros evaluating to target 0.

t3_01corner

Input{"num":"105","target":5}

Expected["1*0+5","10-5"]

⏱ Performance - must finish in 2000ms

Expressions with valid leading zero handling: '05' is invalid, so '1*0+5' and '10-5' are valid.

💡 Check for leading zeros in operands and skip invalid ones.

💡 Operands like '05' are invalid; only '0' alone is valid zero operand.

💡 Implement condition to break loop if operand starts with '0' and length > 1.

Why it failed: Incorrectly allowing operands with leading zeros like '05'. Fix by adding check to skip operands with leading zeros except single '0'. This is the leading zero validation test.

✓ Correctly handles leading zero constraints.

t3_02corner

Input{"num":"1234","target":11}

Expected["1+2*3+4","1*2+3+4","1+2+3+4"]

⏱ Performance - must finish in 2000ms

Expressions that require correct multiplication undo logic to evaluate properly. Note '1+2+3+4' also evaluates to 11 and is valid.

💡 Track last operand to correctly handle multiplication precedence.

💡 When adding '*', subtract last operand and add last operand multiplied by current.

💡 Update evaluated value as evaluated - last_operand + last_operand * current.

Why it failed: Incorrect evaluation of expressions with multiplication due to missing undo logic. Fix by tracking last operand and adjusting evaluated value accordingly. Also include all valid expressions like '1+2+3+4'. This is the multiplication undo bug test.

✓ Correctly evaluates expressions with multiplication.

t3_03corner

Input{"num":"222","target":6}

Expected["2+2+2","2+2*2","2*2*2"]

⏱ Performance - must finish in 2000ms

Tests that operators are used exactly once per split and no unbounded reuse of operands. '2+2*2' also evaluates to 6 and is valid.

💡 Ensure each digit is used exactly once in order without reuse.

💡 Do not treat problem as unbounded operator insertion; only between digits.

💡 Backtrack by moving index forward and not reusing previous digits.

Why it failed: Incorrectly reusing digits or generating duplicate expressions due to incorrect index advancement. Fix by advancing index correctly in recursion to use each digit exactly once and avoid duplicates. Also include all valid expressions like '2+2*2'. This is the 0/1 usage constraint test.

✓ Correctly uses each digit once and generates valid expressions.

t4_01performance

Input{"num":"1234567890","target":100}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=10 with backtracking O(4^n) complexity must complete within 2 seconds.

💡 Backtracking has exponential time complexity O(4^n).

💡 Prune branches early when partial evaluation cannot reach target.

💡 Use efficient string building and memoization if possible.

Why it failed: Solution times out due to exponential complexity O(4^n). Optimize by pruning invalid branches and using efficient string operations.

✓ Solution completes within time limit confirming expected complexity.

Practice

1. Consider the following Python function implementing space-optimized bottom-up DP for edit distance. What is the value of current[1] after the first iteration of the inner loop when calling minDistance("abc", "ac") during the iteration where i = 2?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Identify iteration i=2 corresponds to last character 'c' in "abc"

   At i=2, word1[i] = 'c'. The inner loop runs j=1 to 0 for word2="ac".

2. Step 2: Compute current[1] when j=1 (word2[1] = 'c')

   Since word1[2] == word2[1] ('c' == 'c'), current[1] = next_row[2]. Initially, next_row = [2,1,0], so next_row[2] = 0.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matching chars yield current[j] = next_row[j+1] = 0 [OK]

Hint: Matching chars copy diagonal DP value [OK]

Common Mistakes:

• Off-by-one indexing in j or i
• Confusing current and next_row arrays

2. Consider the following Python code implementing the optimal two-pointer approach for the smallest range covering k lists. Given the input nums = [[1,5,8],[4,12],[7,8,10]], what is the final smallest range returned by the function?

easy

A. [5, 7]

B. [4, 8]

C. [4, 7]

D. [7, 8]

Solution

1. Step 1: Merge and sort all elements with their list indices

   Merged array: [(1,0),(4,1),(5,0),(7,2),(8,0),(8,2),(10,2),(12,1)]

2. Step 2: Use two pointers to find minimal range covering all lists

   Sliding window covers all lists first at [4,7], then [4,8]. The range [4,7] has width 3, and [4,8] has width 4. The minimal range is [4,7].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Range [4,7] covers all lists with minimal width [OK]

Hint: Trace merged array and sliding window coverage [OK]

Common Mistakes:

• Off-by-one in window boundaries
• Forgetting to update have when shrinking window

3. What is the time complexity of the optimized approach that uses sorting, offline queries, and a bitwise trie for the Maximum XOR With Element From Array problem, given n elements in nums and q queries, assuming 32-bit integers?

medium

A. O((n + q) * log(maxNum))

B. O((n + q) * 32)

C. O(n * log(maxNum) * q)

D. O(n * q)

Solution

1. Step 1: Analyze sorting and offline queries

   Sorting nums and queries takes O(n log n + q log q), dominated by O((n + q) log (n + q)) which is less than main complexity.

2. Step 2: Analyze trie operations

   Each insertion and query takes O(log(maxNum)) = O(32) for 32-bit integers. Total insertions = n, total queries = q.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Combined complexity is O((n + q) * log(maxNum)) [OK]

Hint: Trie ops per element and query scale with log(maxNum) [OK]

Common Mistakes:

• Confusing n*q brute force with optimized approach
• Ignoring log(maxNum) factor
• Assuming linear time per query

4. Consider the following buggy code snippet for the optimal median of two sorted arrays. Which line contains the subtle bug that can cause incorrect median calculation or runtime error?

medium

A. Line 10: max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]

B. Line 7: i = (low + high) // 2

C. Line 17: elif max_left_nums1 > min_right_nums2:

D. Line 2: if len(nums1) < len(nums2): nums1, nums2 = nums2, nums1

Solution

1. Step 1: Check array swap condition

   The code swaps arrays only if len(nums1) < len(nums2), which is incorrect. It should swap if nums1 is larger to ensure binary search on smaller array.

2. Step 2: Consequences of wrong swap

   Without correct swap, binary search range can be large, causing inefficiency or index errors.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap condition reversed causes subtle bugs [OK]

Hint: Swap arrays so binary search is on smaller one [OK]

Common Mistakes:

• Swapping arrays incorrectly or not at all
• Off-by-one errors in partition indices
• Incorrect median calculation for odd/even lengths

5. Suppose the problem is modified so that each element in nums can be used multiple times for XOR queries (i.e., unlimited reuse), and queries remain the same. Which of the following changes to the optimized approach is correct to handle this variant efficiently?

hard

A. No change needed; the existing trie approach already supports unlimited reuse

B. Use a dynamic programming approach over XOR states instead of a trie

C. Modify the trie to store counts of inserted elements and adjust maxXor to consider reuse

D. Sort queries and nums but do not insert elements multiple times; reuse is implicit

Solution

1. Step 1: Understand reuse impact

   Unlimited reuse means elements can be XORed multiple times, changing the problem semantics.

2. Step 2: Adjust trie to track counts

   Trie nodes must store counts of inserted elements to allow multiple traversals representing reuse.

3. Step 3: Modify maxXor accordingly

   maxXor must consider paths with repeated elements, enabled by counts, to find max XOR with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Trie with counts supports reuse; naive trie does not [OK]

Hint: Reuse requires tracking counts in trie nodes [OK]

Common Mistakes:

• Assuming no change needed
• Switching to DP unnecessarily
• Ignoring reuse in insertion logic