addBinary

/**
 * Interview Question:
 * Given two binary strings, return their sum as a binary string.
 *
 * Example:
 * addBinary("11", "1") -> "100"
 * addBinary("1010", "1011") -> "10101"
 *
 * Input:
 * a = "1010"
 * b = "1011"
 *
 * Output:
 * "10101"
 *
 * Requirements:
 * - Do not convert the full strings to decimal numbers
 * - Add digits from right to left, just like manual addition
 * - Track carry when the digit sum is 2 or 3
 * - Return "0" when the final result is empty
 *
 * Answer:
 * Use two pointers starting at the end of both strings. At each step, add the
 * current bits plus carry. The output bit is sum % 2, and the next carry is
 * Math.floor(sum / 2). Continue while either pointer has digits or carry exists.
 *
 * Complexity:
 * O(max(a.length, b.length)) time and O(max(a.length, b.length)) space.
 *
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
export default function addBinary(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  let result = "";

  while (i >= 0 || j >= 0 || carry > 0) {
    const bitA = i >= 0 ? Number(a[i]) : 0;
    const bitB = j >= 0 ? Number(b[j]) : 0;
    const sum = bitA + bitB + carry;

    result = `${sum % 2}${result}`;
    carry = Math.floor(sum / 2);

    i--;
    j--;
  }

  return result || "0";
}