Jobs

Interviews

Discussions

Find the XOR of Numbers Which Appear Twice

Easy

Asked by:

6 views

Topics:

ArraysBit Manipulation

You are given an array nums, where each number in the array appears either once or twice.

Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice.

Example 1:

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

Output: 1

Explanation:

The only number that appears twice in nums is 1.

Example 2:

Input: nums = [1,2,3]

Output: 0

Explanation:

No number appears twice in nums.

Example 3:

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

Output: 3

Explanation:

Numbers 1 and 2 appeared twice. 1 XOR 2 == 3.

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 50
Each number in nums appears either once or twice.

Try coding it in LeetCode

Find the XOR of Numbers Which Appear Twice

Easy

Asked by:

6 views

Topics:

ArraysBit Manipulation

You are given an array nums, where each number in the array appears either once or twice.

Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice.

Example 1:

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

Output: 1

Explanation:

The only number that appears twice in nums is 1.

Example 2:

Input: nums = [1,2,3]

Output: 0

Explanation:

No number appears twice in nums.

Example 3:

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

Output: 3

Explanation:

Numbers 1 and 2 appeared twice. 1 XOR 2 == 3.

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 50
Each number in nums appears either once or twice.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Could the numbers be negative, zero, or very large?
What should I return if no numbers appear exactly twice in the input array?
Is the input array guaranteed to have an even number of elements? If not, how should I handle an odd number of elements?
Can the input array contain null or empty values? If so, how should I handle those scenarios?
Is the order of the numbers in the returned XOR value important? Or can I return them in any order?

Brute Force Solution

Approach

The brute force approach to finding the XOR of numbers that appear twice involves checking each number to see how many times it appears. If a number appears exactly twice, we include it in our XOR calculation. Essentially, we're going through every possible pair combination to identify duplicates.

Here's how the algorithm would work step-by-step:

For each number in the collection, compare it to every other number in the collection.
If you find a number that is identical to the first number, increase a counter for that first number.
After comparing the first number to all other numbers, check the counter. If the counter shows that the number appeared exactly twice, save that number.
Repeat this process for every number in the collection.
Once you have identified all the numbers that appeared exactly twice, perform the XOR operation on them. Start with a result of zero. XOR the first number that appears twice with zero, then XOR that result with the second number that appears twice, and so on.
The final result of all the XOR operations is the answer.

Code Implementation

def find_xor_of_numbers_which_appear_twice(number_collection):
    twice_appearing_numbers = []

    for current_index in range(len(number_collection)):
        appearance_counter = 0
        current_number = number_collection[current_index]

        for comparison_index in range(len(number_collection)):
            if number_collection[comparison_index] == current_number:
                appearance_counter += 1

        # We check if the number appeared exactly twice.
        if appearance_counter == 2:

            twice_appearing_numbers.append(current_number)

    xor_result = 0

    # XOR all the numbers that appeared twice.
    for number in twice_appearing_numbers:

        xor_result ^= number

    # Return the final XOR result.
    return xor_result

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm involves iterating through the input array of size n to check the frequency of each number. For each number, we compare it with every other number in the collection to count its occurrences. This nested iteration means that, for each of the n numbers, we potentially perform n comparisons. Therefore, the total number of operations is proportional to n * n, giving a time complexity of O(n²).

Space Complexity

O(1) – The described brute force approach iterates through the input collection, comparing each number with every other number using nested loops. It uses a counter variable to track the number of occurrences for each number and a variable to store the XOR result. These variables consume a constant amount of memory regardless of the input size N, where N is the number of elements in the input collection. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to cleverly use a mathematical trick to isolate the numbers that appear exactly twice. This avoids needing to count how many times each number shows up, making it much faster.

Here's how the algorithm would work step-by-step:

Imagine you have a magic box. When you put a number into it, and then put the same number in again, it disappears.
Now, put all the numbers from the list into the magic box.
Any number that appeared twice will have cancelled itself out.
At the end, the only numbers left in the magic box are the ones that appeared exactly twice (after their pairs were removed).
Combine the numbers remaining in the magic box into a single final number, which is our answer.

Code Implementation

def find_xor_of_numbers_which_appear_twice(numbers):
    xor_sum = 0

    # XORing all numbers cancels out those appearing an even number of times
    for number in numbers:
        xor_sum ^= number

    result = 0

    # Since XOR cancels pairs, what's left are those that appear twice
    for number in numbers:
        if numbers.count(number) == 2:

            # We XOR to get the final result as specified
            result ^= number

    # The XOR of numbers appearing only twice
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the list of n numbers performing an XOR operation on each number. Since the XOR operation takes constant time, and each number is processed only once, the overall time complexity is directly proportional to the number of elements in the input list, resulting in O(n) time complexity.

Space Complexity

O(1) – The plain English explanation describes a 'magic box' where numbers are effectively XORed. This implies we only need a variable to store the cumulative XOR result. No additional data structures like lists or hash maps are mentioned or required. Therefore, the auxiliary space used remains constant regardless of the input size N, where N is the number of elements in the input list. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0, as there are no numbers to XOR.
Array with only one element	Return 0, as there are no pairs of numbers.
Array with no numbers appearing twice	Return 0, as the XOR of no numbers is 0.
Array with all numbers appearing an even number of times, except two appearing twice.	The solution correctly identifies and XORs the two numbers appearing twice.
Array containing negative numbers	The XOR operation works correctly with negative numbers represented in two's complement.
Array containing zero values	The XOR operation handles zeros correctly (number XOR 0 = number).
Large array with many duplicates (close to max array size)	Ensure the chosen approach (e.g., hash map) has sufficient memory and scales efficiently (O(n) time complexity).
Integer overflow during XOR operation with large numbers	Use a data type large enough to hold the result of XOR operations (e.g., long in Java) or consider using bitwise operations within a modular arithmetic to prevent overflow.

Empty input array

How to Handle:

Return 0, as there are no numbers to XOR.

Array with only one element

How to Handle:

Return 0, as there are no pairs of numbers.

Array with no numbers appearing twice

How to Handle:

Return 0, as the XOR of no numbers is 0.

Array with all numbers appearing an even number of times, except two appearing twice.

How to Handle:

The solution correctly identifies and XORs the two numbers appearing twice.

Array containing negative numbers

How to Handle:

The XOR operation works correctly with negative numbers represented in two's complement.

Array containing zero values

How to Handle:

The XOR operation handles zeros correctly (number XOR 0 = number).

Large array with many duplicates (close to max array size)

How to Handle:

Ensure the chosen approach (e.g., hash map) has sufficient memory and scales efficiently (O(n) time complexity).

Integer overflow during XOR operation with large numbers

How to Handle:

Use a data type large enough to hold the result of XOR operations (e.g., long in Java) or consider using bitwise operations within a modular arithmetic to prevent overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Could the numbers be negative, zero, or very large?
What should I return if no numbers appear exactly twice in the input array?
Is the input array guaranteed to have an even number of elements? If not, how should I handle an odd number of elements?
Can the input array contain null or empty values? If so, how should I handle those scenarios?
Is the order of the numbers in the returned XOR value important? Or can I return them in any order?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each number in the collection, compare it to every other number in the collection.
If you find a number that is identical to the first number, increase a counter for that first number.
After comparing the first number to all other numbers, check the counter. If the counter shows that the number appeared exactly twice, save that number.
Repeat this process for every number in the collection.
Once you have identified all the numbers that appeared exactly twice, perform the XOR operation on them. Start with a result of zero. XOR the first number that appears twice with zero, then XOR that result with the second number that appears twice, and so on.
The final result of all the XOR operations is the answer.

Code Implementation

def find_xor_of_numbers_which_appear_twice(number_collection):
    twice_appearing_numbers = []

    for current_index in range(len(number_collection)):
        appearance_counter = 0
        current_number = number_collection[current_index]

        for comparison_index in range(len(number_collection)):
            if number_collection[comparison_index] == current_number:
                appearance_counter += 1

        # We check if the number appeared exactly twice.
        if appearance_counter == 2:

            twice_appearing_numbers.append(current_number)

    xor_result = 0

    # XOR all the numbers that appeared twice.
    for number in twice_appearing_numbers:

        xor_result ^= number

    # Return the final XOR result.
    return xor_result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to cleverly use a mathematical trick to isolate the numbers that appear exactly twice. This avoids needing to count how many times each number shows up, making it much faster.

Here's how the algorithm would work step-by-step:

Imagine you have a magic box. When you put a number into it, and then put the same number in again, it disappears.
Now, put all the numbers from the list into the magic box.
Any number that appeared twice will have cancelled itself out.
At the end, the only numbers left in the magic box are the ones that appeared exactly twice (after their pairs were removed).
Combine the numbers remaining in the magic box into a single final number, which is our answer.

Code Implementation

def find_xor_of_numbers_which_appear_twice(numbers):
    xor_sum = 0

    # XORing all numbers cancels out those appearing an even number of times
    for number in numbers:
        xor_sum ^= number

    result = 0

    # Since XOR cancels pairs, what's left are those that appear twice
    for number in numbers:
        if numbers.count(number) == 2:

            # We XOR to get the final result as specified
            result ^= number

    # The XOR of numbers appearing only twice
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0, as there are no numbers to XOR.
Array with only one element	Return 0, as there are no pairs of numbers.
Array with no numbers appearing twice	Return 0, as the XOR of no numbers is 0.
Array with all numbers appearing an even number of times, except two appearing twice.	The solution correctly identifies and XORs the two numbers appearing twice.
Array containing negative numbers	The XOR operation works correctly with negative numbers represented in two's complement.
Array containing zero values	The XOR operation handles zeros correctly (number XOR 0 = number).
Large array with many duplicates (close to max array size)	Ensure the chosen approach (e.g., hash map) has sufficient memory and scales efficiently (O(n) time complexity).
Integer overflow during XOR operation with large numbers	Use a data type large enough to hold the result of XOR operations (e.g., long in Java) or consider using bitwise operations within a modular arithmetic to prevent overflow.

Empty input array

How to Handle:

Return 0, as there are no numbers to XOR.

Array with only one element

How to Handle:

Return 0, as there are no pairs of numbers.

Array with no numbers appearing twice

How to Handle:

Return 0, as the XOR of no numbers is 0.

Array with all numbers appearing an even number of times, except two appearing twice.

How to Handle:

The solution correctly identifies and XORs the two numbers appearing twice.

Array containing negative numbers

How to Handle:

The XOR operation works correctly with negative numbers represented in two's complement.

Array containing zero values

How to Handle:

The XOR operation handles zeros correctly (number XOR 0 = number).

Large array with many duplicates (close to max array size)

How to Handle:

Ensure the chosen approach (e.g., hash map) has sufficient memory and scales efficiently (O(n) time complexity).

Integer overflow during XOR operation with large numbers

How to Handle:

Use a data type large enough to hold the result of XOR operations (e.g., long in Java) or consider using bitwise operations within a modular arithmetic to prevent overflow.