DevExCode

67. Add Binary

MathStringBit ManipulationSimulation

Explanation

To solve this problem, we can iterate through the two input strings from right to left, perform binary addition, and keep track of the carry. We start by initializing an empty result string and variables to store the current index of each input string, the sum of the current bits, and the carry. We add the corresponding bits from both strings along with the carry, update the result string, and calculate the new carry. Finally, we handle any remaining carry if present.

Algorithm:

  1. Initialize variables i and j to the length of strings a and b minus one respectively, and carry to 0.
  2. Initialize an empty string result to store the sum.
  3. Loop while i >= 0, j >= 0, or carry > 0.
    • Calculate the sum of bits at indices i and j.
    • Update the result string and carry based on the sum.
    • Decrement i and j.
  4. Reverse the result string and return it.

Time Complexity: O(max(N, M)), where N and M are the lengths of input strings a and b.

Space Complexity: O(max(N, M)), for the space used by the result string.

View Leetcode Problem
class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        StringBuilder result = new StringBuilder();
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            
            result.append(sum % 2);
            carry = sum / 2;
        }
        
        return result.reverse().toString();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question