Solution by AndrewJGregory


  • 0
    A

    Approach #1 Convert to Binary and Back [Accepted]

    Intuition

    "Flipping" the bits of a number's binary representation is a conditional: if the bit is a 0, it should be a 1. If the bit is a 1, then it should be a 0. Once we successfully "flip" the bits, then we can convert back to base 10 for the answer.

    Algorithm

    Using native methods in Ruby and JavaScript, the steps are as follows:

    1. Convert the input into base 2 (binary) string representation.
    2. Iterate through the string and "flip" each bit, bit by bit, producing the number's complement in string form in base 2.
    3. Convert the complement back to base 10 (decimal), to find the final answer.

    Note: the "2" in the last lines of both solutions converts the complement string representation into base 10 because when the string is in the same base as the desired base for parseInt or .to_i, the resultant number is in base 10.

    In ruby, this looks like:

      687.to_s(2) # "1010101111"
      "1010101111".to_i(2) # 687
    

    Solutions

    Ruby

    def find_complement(num)
      binary = num.to_s(2)
      flipped = binary.chars.map { |digit| digit == '0' ? '1' : '0' }
      complement = flipped.join
      complement.to_i(2)
    end
    

    JavaScript

    var findComplement = function(num) {
      const binary = num.toString(2);
      const flipped = binary.split("").map(digit => (digit === "0" ? "1" : "0"));
      const complement = flipped.join("");
      return parseInt(complement, 2);
    };
    

    Complexity Analysis

    • Time complexity : O(n)

    n is the string's length of the input number in binary that we iterate over because each bit needs to be flipped.

    • Space complexity : O(n)

    n is also the string's length of the input number in binary.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.