Integer Arithmetic on Decimal Strings
You are given two non-negative integers represented as strings of decimal digits. You have access to two primitive oracles:
- `single_add(a, b)`: adds two single digits (0-9) and returns the result (0-18)
- `single_mul(a, b)`: multiplies two single digits (0-9) and returns the result (0-81)
Using only these primitives, implement:
1. `add(a, b)` -- addition of two decimal strings with correct carry propagation
2. `multiply(a, b)` -- multiplication of two decimal strings using grade-school long multiplication
**Constraints:**
-
\le |a|, |b| \le 10^4$
- Inputs contain only characters `'0'`-`'9'`, no leading zeros (except the number `"0"` itself)
- You may not convert the entire string to an integer
**Example 1:**
```
Input: a = "123", b = "456"
add(a, b) -> "579"
multiply(a, b) -> "56088"
```
**Example 2:**
```
Input: a = "999", b = "1"
add(a, b) -> "1000"
multiply(a, b) -> "999"
```
Analyze the time complexity of both operations.
Open the full interactive solver, hints, and worked solution →