Grind75 Notes
  • README
  • week-1
    • Two Sum
    • Valid Parentheses
    • Merge Two Sorted Lists
    • Best Time to Buy and Sell Stock
    • Valid Palindrome
    • Invert Binary Tree
    • Valid Anagram
    • Binary Search
    • Flood Fill
    • Lowest Common Ancestor of a Binary Search Tree
    • Balanced Binary Tree
    • Linked List Cycle
    • Implement Queue using Stacks
  • week-2
    • First Bad Version
    • Ransom Note
    • Climbing Stairs
    • Longest Palindrome
    • Reverse Linked List
    • Majority Element
    • Add Binary
    • Diameter of Binary Tree
    • Middle of the Linked List
    • Maximum Depth of Binary Tree
    • Contains Duplicate
    • Maximum Subarray
  • week-3
    • Insert Interval
    • 01 Matrix
    • K Closest Points to Origin
    • Longest Substring Without Repeating Characters
    • 3Sum
    • Binary Tree Level Order Traversal
    • Clone Graph
    • Evaluate Reverse Polish Notation
  • week-4
    • Course Schedule
    • Implement Trie (Prefix Tree)
    • Coin Change
    • Product of Array Except Self
    • Min Stack
    • Validate Binary Search Tree
    • Number of Islands
    • Rotting Oranges
  • week-5
    • Search in Rotated Sorted Array
    • Combination Sum
    • Permutations
    • Merge Intervals
    • Lowest Common Ancestor of a Binary Tree
    • Time Based Key-Value Store
    • Accounts Merge
    • Sort Colors
  • week-6
    • Word Break
    • Partition Equal Subset Sum
    • String to Integer (atoi)
    • Spiral Matrix
    • Subsets
    • Binary Tree Right Side View
    • Longest Palindromic Substring
    • Unique Paths
    • Construct Binary Tree from Preorder and Inorder Traversal
  • week-7
    • Container With Most Water
    • Letter Combinations of a Phone Number
    • Word Search
    • Find All Anagrams in a String
    • Minimum Height Trees
    • Task Scheduler
    • LRU Cache
  • week-8
    • Kth Smallest Element in a BST
    • Minimum Window Substring
    • Serialize and Deserialize Binary Tree
    • Trapping Rain Water
    • Find Median from Data Stream
    • Word Ladder
    • Basic Calculator
    • Maximum Profit in Job Scheduling
    • Merge k Sorted Lists
    • Largest Rectangle in Histogram
Powered by GitBook
On this page
  • Problem
  • Pseudocode
  • Solution
  • Time and Space Complexity
  1. week-2

Add Binary

PreviousMajority ElementNextDiameter of Binary Tree

Last updated 2 years ago

Problem

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"

Pseudocode

- parseIns(string), start summing up from the end
    - if > 2, bring forward + 1
    - two main conditions, if bring forward is 1 or 0
        - if bringforward 0
            - 1 + 1 = 0, bringforward++
            - etc etc
        - if bringforward 1
            - 1 + 0 = 1, bringforward++
            - 1 + 1 = 1, bringforward++

Solution

var addBinary = function (a, b) {
  const arr = [];
  const longestArr = a.length > b.length ? a.length : b.length;
  const aEnd = a.length - 1;
  const bEnd = b.length - 1;
  let bringForward = 0;

  for (let i = 0; i < longestArr; i++) {
    const aVal = a[aEnd - i] ? Number(a[aEnd - i]) : 0;
    const bVal = b[bEnd - i] ? Number(b[bEnd - i]) : 0;
    const sum = (aVal + bVal).toString();
    addBringForward(sum);
    // alternatively,
    // const sum = (aVal + bVal);
    // bringForward = sum ? > 1 ? 1 : 0;
    // arr.push(sum % 2);
  }

  function addBringForward(x) {
    if (bringForward === 0) {
      if (x === "2") {
        arr.push("0");
        bringForward = 1;
      } else {
        arr.push(x);
      }
    } else {
      if (x === "0") {
        bringForward = 0;
        arr.push("1");
      } else if (x === "1") {
        bringForward = 1;
        arr.push("0");
      } else if (x === "2") {
        bringForward = 1;
        arr.push("1");
      }
    }
  }

  if (bringForward > 0) {
    arr.push(bringForward.toString());
  }

  return arr.reverse().join("");
};

Time and Space Complexity

Time

  • Loop through array once to sum up numbers - O(N)

  • Other oprations are constant time O(1)

  • Total - O(N)

Space

  • Storing output as array before joining as string - O(N)

  • Total - O(N)

Loading...LeetCode
Logo