Skip to content

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 \oplus 0 = x\);
  • Any number XOR itself is 0, i.e., \(x \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)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

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

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;
    }
}

 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;
    }
};

1
2
3
4
5
6
func singleNumber(nums []int) (ans int) {
    for _, v := range nums {
        ans ^= v
    }
    return
}

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

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

1
2
3
4
5
6
7
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    return nums.reduce((a, b) => a ^ b);
};

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

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;
}

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

Solution 2

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

Comments