Lv.1mathsimulationstring
Add Two Long Binary Numbers
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given two binary strings a and b (only 0 and 1), return their sum as a binary string. Inputs have no leading zeros
except for "0" itself, and the result must not have leading zeros either. The strings can be hundreds of thousands of digits
long, far beyond any built-in fixed-size integer.
Examples
| a | b | result |
|---|---|---|
"11" | "1" | "100" |
"1010" | "1011" | "10101" |
"0" | "0" | "0" |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(a: string, b: string) → string
Constraints
-
a.length,b.length aandbcontain only0and1and have no leading zeros unless the string is"0".
Expected complexity
- Time
- O(N + M)
- Space
- O(N + M)
Examples
| a | b | Expected |
|---|---|---|
"11" | "1" | "100" |
"1010" | "1011" | "10101" |
"0" | "0" | "0" |
Hint
Hint
Add from the last digit with a carry, like column addition: digit = (x + y + carry) % 2, carry = (x + y + carry) / 2. Append
digits to a buffer and reverse once at the end. Prepending each digit (result = digit + result) copies the whole string every
time, which is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1006 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |