LeetCode 136: Single Number

Problem link: https://leetcode.com/problems/single-number/description/

Solution 1:

As the time complexity needs to be linear, the array of integers could be traversed only for once. To remove every pair of same number, XOR is the best option here and it’s also commutative. So, traverse the array and have the XOR operation with each other. The result would be the single number.

public int singleNumber(int[] nums) {
        int result = 0;
        for(int i : nums){
            result ^= i;
        }
        return result;
    }

Time Complexity: O(n)

Solution 2:

Is there a way to improve a the code a little bit? Do we have any unnecessary or duplicate work? These are the best questions to ask to improve the code’s performance.

This solution doesn’t need the auxiliary int to do the XOR operation but pay attention to the for loop. It starts from 1, instead of 0.

public int singleNumber(int[] nums) {
        if(nums.length == 1) return nums[0];
        for(int i=1; i < nums.length; i++){
            nums[0] ^= nums[i];
        }
        return nums[0];
    }

Time Complexity: O(n)