67. Add Binary

 

Adding Binary Numbers with JavaScript: A Step-by-Step Guide

Adding binary numbers is a fundamental task in computer science, often encountered in various coding challenges and real-world applications. In this blog post, we will explore how to add binary numbers using JavaScript. We'll break down the problem, understand the approach, and provide a solution along with its complexity analysis.

The Problem Statement

Given two binary numbers represented as strings, the goal is to add these numbers and return their sum, also as a binary string. For instance, if the inputs are "1010" and "1011", the output should be "10101".

Intuition

The core idea behind this problem is similar to adding decimal numbers, but instead, we deal with binary digits (0 and 1). We need to handle the carry for each bit addition, which is crucial in binary arithmetic.

Approach

Let's break down our approach step by step:

  1. Initialize Variables:

    • carry: This will hold the carryover value during the addition.

    • res: This will store the result as a string.

    • i and j: These pointers will traverse the binary strings a and b from right to left.

  2. Loop Through Both Strings:

    • We continue the loop as long as there are digits to process in either a or b, or if there is a carryover.

  3. Calculate Sum:

    • Initialize sum with the carry value.

    • Add the corresponding digits from a and b to sum if the indices i and j are valid (i.e., non-negative).

    • Use parseInt(a[i]) and parseInt(b[j]) to convert the characters to integers.

  4. Update Result and Carry:

    • Append the least significant bit of the sum (sum % 2) to the result string res.

    • Update the carry by computing the floor division of sum by 2 (Math.floor(sum / 2)).

  5. Move Pointers:

    • Decrement i and j to move to the next digits in a and b.

  6. Return Result:

    • Return the result string res, which contains the binary sum.

Code Implementation

Here’s the JavaScript code implementing the above approach:

javascript
var addBinary = function(a, b) {
    let carry = 0;
    let res = '';
    let i = a.length - 1;
    let j = b.length - 1;

    while (i >= 0 || j >= 0 || carry) {
        let sum = carry;
        if (i >= 0) sum += parseInt(a[i]);
        if (j >= 0) sum += parseInt(b[j]);

        res = (sum % 2) + res;
        carry = Math.floor(sum / 2);

        i--;
        j--;
    }

    return res;   
};

Complexity Analysis

  • Time Complexity: O(N), where N is the length of the longer binary string. We traverse each string once from right to left.

  • Space Complexity: O(N), where N is the length of the result string. This is due to the space required to store the resulting binary string.

Conclusion

Adding binary numbers in JavaScript can be efficiently handled by understanding and implementing basic binary arithmetic. This problem not only helps in grasping binary operations but also enhances problem-solving skills in handling carryover and string manipulation. By following the outlined approach and code, you can effectively add binary numbers and handle edge cases gracefully.

Happy coding!

LeetCode Link : https://leetcode.com/problems/add-binary/solutions/6190289/simple-solution-by-bikash_kumar_giri-kthk/

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more