algoadvance

Leetcode 136. Single Number

Problem Statement

  1. Single Number

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:

Input: nums = [2,2,1]
Output: 1

Input: nums = [4,1,2,1,2]
Output: 4

Input: nums = [1]
Output: 1

Clarifying Questions

  1. Q: Can the array contain negative numbers?
    • A: Yes, the array can contain both negative and positive integers.
  2. Q: What is the size range of the array?
    • A: The array size can range from 1 to (10^4).
  3. Q: Is it guaranteed that there is exactly one single number and all other numbers appear exactly twice?
    • A: Yes, it is guaranteed.

Strategy

To solve this problem efficiently (O(n) time complexity and O(1) extra space), we can take advantage of the properties of the XOR bitwise operation:

  1. XOR of two same numbers is 0 (e.g., a ^ a = 0).
  2. XOR of a number with 0 is the number itself (e.g., a ^ 0 = a).

Thus, if we XOR all the numbers in the array, the numbers that appear twice will cancel out each other, leaving the single number as the result.

Code

Here’s the implementation in C++:

#include <vector>
#include <iostream>

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num; // XOR all elements
        }
        return single;
    }
};

int main() {
    Solution solution;
    
    std::vector<int> test1 = {2, 2, 1};
    std::cout << "Test 1: " << solution.singleNumber(test1) << std::endl; // Output: 1
    
    std::vector<int> test2 = {4, 1, 2, 1, 2};
    std::cout << "Test 2: " << solution.singleNumber(test2) << std::endl; // Output: 4
    
    std::vector<int> test3 = {1};
    std::cout << "Test 3: " << solution.singleNumber(test3) << std::endl; // Output: 1
    
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI