Funcia
Lv.1mathsimulationstring

Add Two Long Binary Numbers

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

abresult
"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

  • 1≤1 \le a.length, b.length ≤500,000\le 500{,}000
  • a and b contain only 0 and 1 and have no leading zeros unless the string is "0".

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

abExpected
"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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251006 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.