Shortest Ruby solution


  • 3
    Y
    def single_number(nums)
      nums.reduce(:^)
    end

  • 0
    V

    Could you (or anyone else) explain why this works if you've got a chance? I understand how bitwise XOR works, and by doing the reduce by hand on a few arrays, I see that it works, but I haven't yet managed to understand why it works---i.e. how the heck you came up with the solution. Thanks!

    Edit: Actually, it seems that this solution only works when the non-pair integer occurs once or or some odd number of times, but does not work when it occurs an even number of times. [1,1,1,1,3,3,2,2].reduce(:^) returns 0, for instance, and so unless I'm missing something this is not a legit solution to the problem. I want my upvote back! :)


  • 0
    C

    @vegangreg
    Hey Greg,

    The above solution is actually just shorthand for the following:

    def single_number(nums)
      nums.reduce { |memo, num| memo ^ num }
    end
    

    With reduce If you specify a block, then for each element in enum the block is passed an accumulator value (memo) and the element. If you specify a symbol instead, then each element in the collection will be passed to the named method of memo. In either case, the result becomes the new value for memo. At the end of the iteration, the final value of memo is the return value for the method.

    In this case the first element of the array is taken as the memo and the second element is taken as the num. They're compared using the bitwise XOR operator and the new result is then stored in memo and will be compared to the third element in the array and so on down the line. The memo's final value is then returned at the end of the iteration.

    The reason your example of [1,1,1,1,3,3,2,2] doesn't work is because of the way that the XOR operator works when comparing each new number to the memo. XOR returns 0 when both the memo and the next element in the array match so if you have an even number of comparisons then the final value of the memo that's returned is going to be zero.


Log in to reply
 

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