136. Single Number

Introduction

Given a non-empty integer array nums, where every element appears twice except for one, find that single element.

You must design and implement an algorithm with linear time complexity that uses 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

Note:

• •
• •
• • Every element appears twice except for one.

Solution Approach

This problem can be solved using <span>bitwise XOR</span> operations.

Here are the properties of XOR operation:

• • Any number XORed with <span>0</span> results in the original number, i.e., ;
• • Any number XORed with itself results in <span>0</span>, i.e., ;

Similarly, in Rust, you can use <span>reduce</span> and <span>fold</span> to perform the calculation, but the return types are slightly different. <span>reduce</span> returns an <span>Option</span> object.

impl Solution {
    // Calculate using XOR method,
    pub fn single_number(nums: Vec) -> i32 {
        // nums.into_iter().fold(0, |xor, x| xor ^ x)
        nums.into_iter().reduce(|xor, x| xor ^ x).unwrap_or(0)
    }
}