136. Single Number

Description

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

Solutions

Solution 1: Bitwise Operation

The XOR operation has the following properties:

  • Any number XOR 0 is still the original number, i.e., x⊕0=xx \oplus 0 = x;
  • Any number XOR itself is 0, i.e., x⊕x=0x \oplus x = 0;

Performing XOR operation on all elements in the array will result in the number that only appears once.

The time complexity is O(n)O(n), where nn is the length of the array. The space complexity is O(1)O(1).

Python Code
1
2
3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

Java Code
1
2
3
4
5
6
7
8
9

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int v : nums) {
            ans ^= v;
        }
        return ans;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int v : nums) {
            ans ^= v;
        }
        return ans;
    }
};

Go Code
1
2
3
4
5
6

func singleNumber(nums []int) (ans int) {
	for _, v := range nums {
		ans ^= v
	}
	return
}

TypeScript Code
1
2
3

function singleNumber(nums: number[]): number {
    return nums.reduce((r, v) => r ^ v);
}

Rust Code
1
2
3
4
5
6
7

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        nums.into_iter()
            .reduce(|r, v| r ^ v)
            .unwrap()
    }
}

JavaScript Code
1
2
3
4
5
6
7

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    return nums.reduce((a, b) => a ^ b);
};

C# Code
1
2
3
4
5

public class Solution {
    public int SingleNumber(int[] nums) {
        return nums.Aggregate(0, (a, b) => a ^ b);
    }
}

C Code
1
2
3
4
5
6
7

int singleNumber(int* nums, int numsSize) {
    int ans = 0;
    for (int i = 0; i < numsSize; i++) {
        ans ^= nums[i];
    }
    return ans;
}

Swift Code
1
2
3
4
5

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        return nums.reduce(0, ^)
    }
}

Solution 2

Java Code
1
2
3
4
5

class Solution {
    public int singleNumber(int[] nums) {
        return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
    }
}