Add Binary Strings
Easy About 10 min Free, no account needed
Add two binary numbers far too long for any built-in integer.
The brief
Given two binary strings a and b (no leading zeros except "0" itself),
return their sum as a binary string.
Convert.ToInt64(s, 2) works right up until the hidden test hands you a
300,000-bit number, far beyond any built-in integer. You will have to add the
two strings directly, without converting them to a numeric type.
Adding the strings directly is only half the job. Growing the answer with
result = digit + result (or sb.Insert(0, digit)) copies everything built so
far on every bit, so it is O(n^2) and will not finish the hidden test. Append
as you go and reverse once at the end.
Starter code
using System;
public class Solution
{
// TODO: return the sum of two binary strings, as a binary string.
public string AddBinary(string a, string b)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- String processing
- Parse, scan and match text character by character with correct edge cases.
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Excel Column Number Easy Free Spreadsheet columns are base-26 with no zero digit.
- Multiply Numeric Strings Medium Free Schoolbook multiplication of numbers thousands of digits long.
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.