136. Single Number

📝 Problem Details

• Title: 136. Single Number
• Link: https://leetcode.com/problems/single-number/
• Difficulty: Easy
• Tags/Categories: Bit-Manipulation

Input: non-empty array of integers nums every element appears twice except for one find the element that does not appear twice Constraints: linear O(n) time complexity , constant O(1) space complexity

💭What Were My Initial Thoughts?

naive approach not considering constraints:
- build a frequency map and return the number with a frequency less than 2
	- O(n) time complexity but also uses O(n) space
- we could sort the input array and check neighbouring elements
	- it would be constant in space but O(n log n) time complexity 

💡 Explanation of Solution

*XORing all indices and elements results in the missing number, as all pair elements cancel out*

⌛ Complexity Analysis

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

💻 Implementation of Solution

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