67. Add Binary
Add Binary (LeetCode 67) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Multiply Strings (Manual Simulation) subpattern.
How to solve Add Binary
Add Binary is a Multiply Strings problem, part of String Manipulation Patterns. Learn to multiply large numbers represented as strings using manual simulation of multiplication.
Work towards the solution in these steps:
- Consider how you would add two numbers digit by digit, and think about which data structure can help you build the result efficiently.
- Since the inputs are binary strings, think about processing them from right to left, simulating addition like you would on paper.
- Keep track of a carry value when adding each pair of bits, just like in manual binary addition.
The reference solution runs in O(n) time and O(1) space.
The Add Binary solution and editorial walks through the full approach with reference code.
Problem statement
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
Constraints:
- 1 <= a.length, b.length <= 10^4 - a and b consist only of '0' or '1' characters. - Each string does not contain leading zeros except for the zero itself.
Topics and companies
Topics: Math, String.
Reported in interviews at Facebook, Amazon, ByteDance.
How to practise Add Binary on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Add Binary in the code editor, or read the Add Binary editorial for a worked solution with its approach and complexity analysis.
Where Add Binary sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Multiply Strings (Manual Simulation) subpattern
- The full DSA patterns sheet
Problems related to Add Binary
Other problems that use the same Multiply Strings (Manual Simulation) and String Manipulation Patterns techniques:
- Add to Array-Form of Integer — Easy, same subpattern
- Multiply Strings — Medium, same subpattern
- Plus One — Easy, same subpattern
- Concatenation of Array — Easy, same pattern
- Contains Duplicate — Easy, same pattern
- Design HashSet — Easy, same pattern
Add Binary FAQ
What is the LeetCode number of Add Binary?
Add Binary is LeetCode problem 67, rated Easy.
What pattern is used to solve Add Binary?
Add Binary is a Multiply Strings problem. It belongs to the String Manipulation Patterns pattern, in the Multiply Strings (Manual Simulation) subpattern.
What is the time complexity of Add Binary?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Add Binary?
Add Binary has been reported in interviews at Facebook, Amazon, ByteDance.