136. Single Number

• Link: https://leetcode.com/problems/single-number/description/

Question

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.

Approach 1: Brute Force

Intuition

• Count no. of occurances of each element if it is 1 return that element

Algorithm

1. Loop through nums for each element
   1. Declare & initialize count =0
   2. Linear search nums[i] in nums, increment count every time nums[j] == nums[i]
   3. If count equals 1, return nums[i]
2. Return -1;

Code

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		for (int i = 0 ; i < nums.size() ; i++) {
			int count = 0;

			for (int j = 0 ; j < nums.size() ; j++) {
				if (nums[i] == nums[j]) {
					count++;
				}
			}
			
			if (count == 1) return nums[i];
		}
		return -1;
	}
};

Complexity Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$

Approach 2: Better

Intuition

• Use hashing to count the no. of occurances
• Can use map or a vector (array)

Algorithm

1. Declare an unordered_map m
2. loop through nums
   1. Increment m[nums[i]]
3. Iterate through the map m if the value of a key is 1, return that key.

Code

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		unordered_map<int, int> m;
		
		for (int num: nums) {
			m[num]++;
		}
		
		for (pair<int, int> it: m) {
			if (it.second == 1) return it.first;
		}
		
		return -1;
	}
};

Complexity Analysis

• Time Complexity: $O(2n)=O(n)$
• Space Complexity: $O(n)$

Approach 3: Optimal

Intuition

• Bit Manipulation DSA XOR (^)
• 2^2 = 0
• 3^3 = 0
• 2^2^3^3 = 0
• 2^0 = 2
• 0^3 = 3

Algorithm

1. Declare & initialize int x = 0
2. Loop through int num: nums
   1. x = x ^ num, XOR
3. Return x;

Code

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

Complexity Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$