Integer Arithmetic on Decimal Strings
You are given two non-negative integers represented as strings of decimal digits, plus an operation selector. Implement a single function:
``` arith(op, a, b) ```
where: - op is either 'add' (addition) or 'mul' (multiplication) - a and b are non-negative integers as decimal strings (only characters '0'-'9', no leading zeros except the number "0" itself)
Perform the requested operation using grade-school digit-by-digit arithmetic (addition with carry propagation, or long multiplication). Return the result as a decimal string with no leading zeros. Do not convert the whole string to an integer via int(a).
Constraints: - $1 \le |a|, |b| \le 10^4$ - Inputs contain only characters '0'-'9', no leading zeros (except "0")
Analyze the time complexity of both operations.
Example
arith("mul", "123", "456") -> "56088" -- long multiplication of 123 and 456 yields 56088, returned as a leading-zero-free decimal string. Likewise arith("add", "123", "456") -> "579".
Hints
- Think about how you add two numbers by hand, digit by digit from right to left. The carry is the key piece of state.
- For multiplication, each digit of $b$ times all of $a$ gives a partial product. Shift each partial product by the appropriate power of 10, then sum them with your addition routine.
- The addition routine is $O(\max(n,m))$. For multiplication, you call it $m$ times with strings of length up to $n + m$, giving $O(nm)$ total.
Worked Solution
How to Think About It: This is grade-school arithmetic implemented from scratch. The judge calls a single entry point arith(op, a, b) where op is 'add' or 'mul', and a, b are non-negative integer decimal strings. It dispatches to hand-rolled addition or long multiplication and returns the result as a decimal string with no leading zeros. The only subtlety is managing carries correctly. For addition, walk right-to-left through both strings, adding digits plus carry. For multiplication, compute partial products (one digit of b times all of a), shift them, and accumulate with repeated addition.
Algorithm:
*Addition (op == 'add'):* Scan both strings from right to left. At each position, add the two digits plus the incoming carry. The result modulo 10 is the output digit; the result divided by 10 is the new carry. Continue until both strings and the carry are exhausted, then strip leading zeros.
*Multiplication (op == 'mul'):* For each digit b[j] (right to left), multiply it against every digit of a (right to left), accumulating carries into a partial product. Shift it left by appending len(b)-1-j zeros, then add all partial products together. Short-circuit to '0' if either operand is '0'.
Code:
```python def _add(a, b): result = [] carry = 0 i, j = len(a) - 1, len(b) - 1 while i >= 0 or j >= 0 or carry: d1 = ord(a[i]) - 48 if i >= 0 else 0 d2 = ord(b[j]) - 48 if j >= 0 else 0 s = d1 + d2 + carry result.append(chr(s % 10 + 48)) carry = s // 10 i -= 1 j -= 1 out = ''.join(reversed(result)).lstrip('0') return out or '0'
def _mul(a, b): if a == '0' or b == '0': return '0' result = "0" for j in range(len(b) - 1, -1, -1): carry = 0 partial = [] bj = ord(b[j]) - 48 for i in range(len(a) - 1, -1, -1): prod = (ord(a[i]) - 48) * bj + carry partial.append(chr(prod % 10 + 48)) carry = prod // 10 if carry: partial.append(chr(carry + 48)) partial_str = ''.join(reversed(partial)) partial_str += '0' * (len(b) - 1 - j) result = _add(result, partial_str) return result.lstrip('0') or '0'
def arith(op, a, b): # op is 'add' or 'mul'. a and b are non-negative integer decimal strings. if op == 'add': return _add(a, b) elif op == 'mul': return _mul(a, b) raise ValueError("unknown op: " + str(op))
```
Complexity:
Let $n = |a|$ and $m = |b|$.
- *Addition:* $O(\max(n, m))$ single-digit additions, constant work per step.
- *Multiplication:* The outer loop runs $m$ times; each iteration does $n$ single-digit multiplications plus one addition of length up to $n + m$. Overall $O(nm)$.
Answer: Addition runs in $O(\max(n, m))$ and multiplication runs in $O(nm)$ using only per-digit operations. This is the grade-school algorithm -- optimal without advanced techniques like Karatsuba. Note the earlier version defined separate add/multiply functions, but the judge only ever calls arith(op, a, b), so the dispatch must live there.
Intuition
This problem tests whether you can implement arithmetic from first principles -- something most people take for granted. The core lesson is that all multi-digit arithmetic reduces to single-digit operations plus carry management. Addition is a single right-to-left pass with a one-bit carry. Multiplication decomposes into $O(nm)$ single-digit multiplications arranged as partial products, exactly like the algorithm you learned in school.
In practice, this shows up in arbitrary-precision arithmetic libraries (Python's built-in big integers, Java's BigInteger, etc.). For very large numbers, faster algorithms like Karatsuba ($O(n^{1.585})$) or FFT-based multiplication ($O(n \log n)$) exist, but the grade-school method is the baseline and often sufficient for moderate sizes.