Skip to content
Single Number LeetCode C++

Single Number in Array LeetCode C++

Program to Find the Single Number in an Array LeetCode problem. In this question, we have an array containing numbers in pairs, but a single number appears only once in an array and we need to print that out.

Note: Our solution needs to have a Linear Runtime Complexity and without using extra memory i.e Constant Space

Examples

Input: [1,2,3,1,3]
Output: 2

Input:[3]
Output:3

Solution Approach

  • Time Complexity O(N)
  • Space Complexity O(1)

Space is constant so we cannot sort the array, but we can use the XOR way, recently when I solved a similar problem i.e to find a single missing number in an array, where we use XOR, same numbers cancel each other

1^1^2 = 2
1^3^4^1^4 = 3

Code in C++ Single Number Leetode

class Solution {
public:
    int singleNumber(vector<int>& nums) {
         int miss = nums[0];
        for(int i = 1; i < nums.size(); i++)
            miss ^= nums[i];
        return miss;
    }
};

Conclusion

Link to Problem Single Number LeetCode, XOR can be very useful in such cases, also read Missing Number LeetCode for more explanation. This post is part of my #30DaysChallenge to write a blog post every day on what I learn.

All the Best ~ Abhiram Reddy

Tags: