Long Division on Text Numbers
HardMath & Geometry
Problem
Two non-negative integers are given as decimal strings: a dividend with up to 500 digits and a positive divisor with up to 200 digits. Both are far too large for built-in integer types.
Return the integer quotient ⌊dividend / divisor⌋ as a decimal string without leading zeros. Do not convert the inputs to big integers.
Example 1
- Input:
- dividend = "1000", divisor = "7"
- Output:
- "142"
7 · 142 = 994 and 7 · 143 = 1001 > 1000.
Example 2
- Input:
- dividend = "5", divisor = "7"
- Output:
- "0"
Example 3
- Input:
- dividend = "12345678901234567890", divisor = "12345"
- Output:
- "1000054994024671"
Constraints
- 1 ≤ dividend.length ≤ 500, 1 ≤ divisor.length ≤ 200
- Digits only, no leading zeros except the number "0" itself
- divisor ≠ "0"
Hint
Show the first hint
Do it like long division on paper: bring down one digit of the dividend at a time into a running remainder.
Walkthrough
How to approach it
01Clarify before coding
- Is the quotient rounded down? Yes, ⌊dividend / divisor⌋; the remainder is discarded.
- Can the dividend be smaller than the divisor? Yes: the answer is "0".
- Can I use repeated subtraction of the divisor from the whole dividend? Only per digit; on the whole number it could take 10^300 steps.
02Brute force
Subtract the divisor from the dividend until it becomes smaller, counting the subtractions.
Cost: O(quotient · n): the quotient itself can have 300 digits, so this never finishes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.