Algorithm Puzzles: Single Number

Posted on Edited on In Views: Word count in article: 103 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Single Number

Puzzle

Puzzle from leetcode:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    static int singleNumber(const vector<int>& nums) {
        int single = nums[0];
        for(auto iter = nums.begin() + 1; iter != nums.end(); ++iter) {
            single ^= *iter;
        }

        return single;
    }
};

T.C.: O(N)
S.C.: O(1)