We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the XOR of Numbers Which Appear Twice

Number: 3428

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

You are given an array nums where each number appears either once or twice. The goal is to return the bitwise XOR of all the numbers that appear twice in the array. If no number appears twice, return 0.

Key Insights

  • The input array contains numbers that appear once or twice, so no number appears more than twice.
  • We can leverage a frequency count (using a hash table) to identify numbers which appear exactly twice.
  • Once identified, compute the XOR of these numbers.
  • XOR has the property that a XOR b is computed bitwise and order does not matter.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the nums array since we iterate through the array to build the frequency count and iterate over the frequency dictionary. Space Complexity: O(n) in the worst case for the frequency count (although n is small as per constraints).

Solution

We first traverse the given array and record the frequency of each number using a hash table (or dictionary). Then, we iterate over the entries in the hash table and for every number that appears exactly twice, we apply the XOR operation with an accumulating result. If no number appears twice, our accumulator remains 0. This method efficiently identifies the required numbers and computes the final XOR with a simple and clear two-pass approach over the data.

Code Solutions

# Python solution

def find_xor_of_twice(nums):
    # Initialize a dictionary to store frequency counts.
    frequency = {}
    # Count the occurrences for each number in nums.
    for num in nums:
        # Increase the count if num is already seen; otherwise, initialize count to 1.
        frequency[num] = frequency.get(num, 0) + 1
    
    # Initialize the result to 0.
    xor_result = 0
    # Iterate over the frequency dictionary.
    for num, count in frequency.items():
        # Check if the number appears exactly twice.
        if count == 2:
            # XOR the current result with the number.
            xor_result ^= num
    # Return the final XOR result.
    return xor_result

# Example usage:
print(find_xor_of_twice([1, 2, 1, 3]))  # Output: 1
print(find_xor_of_twice([1, 2, 3]))     # Output: 0
print(find_xor_of_twice([1, 2, 2, 1]))  # Output: 3
← Back to All Questions