1825. Remainder in Any Base
A checksum service receives very long non-negative numbers as text in a base between 2 and 36, using the digits 0 to 9 and then the lowercase letters a to z. It only needs the remainder of each number when divided by m, and the numbers are far too long to convert to a built-in integer.
Given digits, base and m, return the remainder of the number when it is divided by m. Every digit is smaller than base. Aim for O(n) time and O(1) extra space, where n is the length of digits. Be careful that intermediate products can exceed 32 bits when m is large.
Example 1
- Input:
- digits = "1172", base = 8, m = 7
- Output:
- 4
- Explanation:
1172 in octal is 634, and 634 mod 7 is 4.
Example 2
- Input:
- digits = "ff", base = 16, m = 10
- Output:
- 5
- Explanation:
ff in hexadecimal is 255, and 255 mod 10 is 5.
Example 3
- Input:
- digits = "0", base = 2, m = 7
- Output:
- 0
- Explanation:
Zero has remainder 0.
Constraints
2 ≤ base ≤ 36
1 ≤ digits.length ≤ 1000
1 ≤ m ≤ 109
every digit is smaller than base; no leading zeros except the single string "0"
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)