algoadvance

Leetcode 3158. Find the XOR of Numbers Which Appear Twice

Problem Statement

You are given an array of integers nums where every element appears exactly twice except for one element which appears once. Find the element that appears once.

Clarifying Questions

  1. Input Size: What is the maximum size of the input array?
    • Assuming a reasonable constraint, let’s say the size of nums can go up to 10^6.
  2. Value Range: What is the range of the integer values in the array?
    • Let’s assume the integer values can range from -10^6 to 10^6.
  3. Output: Is there any specific format for the output?
    • The output should simply be the integer that appears only once.

Strategy

We can leverage the XOR bitwise operator to solve this problem efficiently:

  1. XOR Property: a ^ a = 0 and a ^ 0 = a. This means that if we XOR all the numbers together, the numbers that appear twice will cancel each other out, leaving us with the number that appears only once.

  2. Time Complexity: Since we only need a single pass through the array to compute the XOR, the time complexity is O(n), where n is the number of elements in the array.

  3. Space Complexity: We do not need any extra space other than a few variables for the XOR computation, so the space complexity is O(1).

Code

Here is the C++ implementation of the solution:

#include <iostream>
#include <vector>

int findUniqueNumber(const std::vector<int>& nums) {
    int uniqueNumber = 0;
    for (int num : nums) {
        uniqueNumber ^= num;
    }
    return uniqueNumber;
}

int main() {
    std::vector<int> nums;
    int n;
    
    std::cout << "Enter the number of elements: ";
    std::cin >> n;
    
    std::cout << "Enter the elements: ";
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        nums.push_back(x);
    }
    
    int result = findUniqueNumber(nums);
    std::cout << "The element that appears once is: " << result << std::endl;
    
    return 0;
}

Explanation of the Code

  1. Input Handling: We read the number of elements n and then populate the nums array with n integers.
  2. XOR Calculation: We initialize uniqueNumber to 0 and iterate through all elements in nums, applying the XOR operation to uniqueNumber and each element. After the loop, uniqueNumber will hold the element that appears only once.
  3. Output: Finally, we print the element that appears once.

By following this approach, we can efficiently determine the unique element in the array using XOR properties.

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