136. Single Number

Problem statement

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 * 10^4.
-3 * 10^4 <= nums[i] <= 3 * 10^4.
Each element in the array appears twice except for one element which appears only once.

Solution 1: Counting the appearances

Count how many times each element appears in the array. Then return the one appearing only once.

Code

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
int singleNumber(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int n : nums) {
        count[n]++;
    }
    int single;
    for (auto& pair : count) {
        if (pair.second == 1) {
            single = pair.first;
            break;
        }
    }
    return single;
}
int main() {
    vector<int> nums{2,2,1};
    cout << singleNumber(nums) << endl;
    nums = {4,1,2,1,2};
    cout << singleNumber(nums) << endl;
    nums = {1};
    cout << singleNumber(nums) << endl;
}

Output:
1
4
1

Complexity

Runtime: O(N), where N = nums.length.
Extra space: O(N) (not constant, need another solution).

Solution 2: Bitwise exclusive OR

You can also use the bitwise XOR operator to cancel out the duplicated elements in the array. The remain element is the single one.

a XOR a = 0.
a XOR 0 = a.

Code

#include <vector>
#include <iostream>
using namespace std;
int singleNumber(vector<int>& nums) {
    int single = 0;
    for (int n : nums) {
        single ^= n;
    }
    return single;
}
int main() {
    vector<int> nums{2,2,1};
    cout << singleNumber(nums) << endl;
    nums = {4,1,2,1,2};
    cout << singleNumber(nums) << endl;
    nums = {1};
    cout << singleNumber(nums) << endl;
}

Output:
1
4
1

Complexity

Runtime: O(N), where N = nums.length.
Extra space: O(1).

References

https://leetcode.com/problems/single-number/

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.

136. Single Number

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution 1: Counting the appearances

Code

Complexity

Solution 2: Bitwise exclusive OR

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution 1: Counting the appearances

Code

Complexity

Solution 2: Bitwise exclusive OR

Code

Complexity

References