Ruby solution (AC, collecting 0's and 1's of the "single number" and converting to Integer )


  • 0
    N

    The solution is rather slow and not laconic. It is easy to understand, though.

    The code is looping through the nums array, after that array_plus and array_minus are produces. The arrays both have 32 elements, each initially is set to 0. Depending on the sign of the "single number" (the number which we try to detect) one of these arrays will finally store only zeros. Another array will store 0's and 1's of the "single number".

    Example:
    if the given nums = [2, 2, 3, 2],
    array_plus will be ---
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

    array_minus will contain zeroes (due to 3 is positive) ---
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    Note, if the "single number" is 0, both arrays will contain only zeros.
    Note, it is assumed that 32 bits is the word length of the processor, hence 32 is the size for the arrays.

    Knowing bits of the "single number" we can convert it to Integer.
    Pitifully, while "011".to_i(2) works for positive numbers, it won't work for two's complement for a negative number.
    But knowing that the the "single number" is negative and what is "two's complement", it is easy to compose a custom method for converting.

    To get the sign of the "single number" immediately after looping through nums, there are "plus" and "minus" flags. These variables are just to store the sum of 1's in the array_plus and array_minus respectively. In the example (given nums = [2, 2, 3, 2]) the "single number" is 3, which is positive. For this "plus" flag value will be 2 (0 + 0 + ...+ 0 + 1 + 1), and "minus" flag value is 0.

    For positive "single number" to_i(2) can be used for converting binary representation to Integer.
    To convert a negative "single number" to Integer please see the code below (commented as #converting the resulting array of bits into Integer).

    # @param {Integer[]} nums
    # @return {Integer}
    def single_number(nums)
      array_plus = Array.new(32, 0) #to store bit counters of positive nums
      array_minus = Array.new(32, 0) #to store bit counters negative nums
    
    
      for i in 0...nums.size do
        # depening on the sign of the "single number" the plus/minus will be above zero
        plus = 0 
        minus = 0
        
        #assume that the processor has 32-bit word length
        bits = 31 
        
        #going through each bit in current item from nums array
        while bits >= 0 do
    
          if nums[i] >= 0
            array_plus[bits] =  (array_plus[bits].to_i + 1)%3 if (nums[i] & 1 != 0)
          else
             array_minus[bits] =  (array_minus[bits].to_i + 1)%3 if (nums[i] & 1 != 0)
          end
          
          #here the plus and minus flags get updated     
          plus = plus + array_plus[bits]
          minus = minus + array_minus[bits]
    
          bits = bits - 1
          nums[i] = nums[i] >> 1
    
        end
      end
    
      #converting the resulting array of bits into Integer 
      if plus > 0
        return array_plus.join("").to_i(2)
        
      elsif minus > 0
        signed = array_minus[0]*(2**31)
        magnitude = 0
            (1..31).each do |index|
              magnitude =  magnitude + array_minus[index]*(2**(31-index))
            end
        return (- signed + magnitude)
      else
        return 0
      end
    end

Log in to reply
 

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