Coding Interview Questions | Add Binary

January 1st, 2024

Add Binary Problem Introduction:

This summary will talk about my solution to the add binary problem as seen on leetcode here.

How do I solve the Add Binary Problem in O(1) time?

Solution

const addBinaryDigits = (a: number, b: number, carry: number) => {
  if (a + b + carry === 3) {
    return { total: 1, isCarry: true };
  }
  if (a + b + carry === 2) {
    return { total: 0, isCarry: true };
  }
  if (a + b + carry === 1) {
    return { total: 1, isCarry: false };
  }

  return { total: 0, isCarry: false };
};

function addBinary(a: string, b: string): string {
  const iterationCount = a.length > b.length ? a.length : b.length;
  let currentIteration = 0;
  let isCarry = false;
  let result = "";
  let paddedA = a.padStart(iterationCount, "0");
  let paddedB = b.padStart(iterationCount, "0");

  while (currentIteration < iterationCount) {
    const currentAChar = parseInt(
      paddedA[iterationCount - (currentIteration + 1)]
    );
    const currentBChar = parseInt(
      paddedB[iterationCount - (currentIteration + 1)]
    );

    const { isCarry: isNewCarry, total } = addBinaryDigits(
      currentAChar,
      currentBChar,
      isCarry ? 1 : 0
    );

    result = total + result;
    isCarry = isNewCarry;
    currentIteration += 1;
  }

  if (isCarry) {
    return "1" + result;
  }
  return result;
}

Add Binary Problem Summary:

Solution Summary

1. addBinaryDigits Function: The solution above first defines a function to add two binary digits and a carry, returning the sum and whether there’s a carry for the next addition.
2. Iteration and Padding: The main function will first determine the number of iterations based on the longer string and pads the shorter string with leading zeros.
3. Binary Digit Processing: Then, the while loop will process the binary digits from right to left, considering the current digits of both input strings as well as the current carry digit if one exists.
4. Result Building: As it iterates, it builds the result string by appending the sum of binary digits from each iteration.
5. Handling Final Carry: At the end of the iteration, the function ensures proper handling of the final carry, if any, and adjusts the result string accordingly.

Complexities

• Time Complexity: The algorithm iterates through the binary digits once, resulting in O(n) time complexity, where n is the length of the longest string between a and b.
• Space Complexity: The algorithm uses O(n) space given the padded string creation.

Can I simplify the solution to the Add Binary Problem?

Bonus Solution

function addBinary(a: string, b: string): string {
  let carry = 0;
  let result = "";

  // Determine the maximum length among input strings
  const maxLength = Math.max(a.length, b.length);

  // Iterate through the strings from right to left
  for (let i = 0; i < maxLength || carry > 0; i++) {
    const digitA = i < a.length ? parseInt(a[a.length - 1 - i]) : 0;
    const digitB = i < b.length ? parseInt(b[b.length - 1 - i]) : 0;

    const sum = digitA + digitB + carry;
    result = (sum % 2) + result;
    carry = sum >= 2 ? 1 : 0;
  }

  return result || "0";
}