Jobs

Interviews

Discussions

Single Number III

Medium

Zomato

3 views

Topics:

ArraysBit Manipulation

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

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

Constraints:

2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each integer in nums will appear twice, only two integers will appear once.

Try coding it in LeetCode

Single Number III

Medium

Zomato

3 views

Topics:

ArraysBit Manipulation

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

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

Constraints:

2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each integer in nums will appear twice, only two integers will appear once.

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 for the integers in the input array? Can they be negative, zero, or very large?
Is it guaranteed that there will always be exactly two single numbers, and all other numbers appear exactly twice?
What should I return if the input array is null or empty?
Is the order of the two unique numbers in the output array significant, or can I return them in any order?
What is the maximum possible size of the input array, and should I be concerned about integer overflow during any calculations?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every number against every other number to see if it has a duplicate. By exhaustively comparing each number to all the others, we can identify the two numbers that appear only once.

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

Take the first number in the collection.
Compare this number to every other number in the collection.
If you find a match, it's not a single number, so move on to the next number.
If you compare it to every other number and don't find a match, remember this number.
Repeat this process for every number in the collection.
After checking all the numbers, you'll have identified the two numbers that appeared only once.

Code Implementation

def single_number_iii_brute_force(numbers):
    single_numbers = []
    for first_index in range(len(numbers)):
        is_single = True

        # Check if the current number is a duplicate
        for second_index in range(len(numbers)):
            if first_index != second_index and numbers[first_index] == numbers[second_index]:
                is_single = False
                break

        # Add to result if no duplicates found
        if is_single:
            single_numbers.append(numbers[first_index])

    return single_numbers

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves iterating through the array of n numbers. For each number, we compare it with every other number in the array to check for duplicates. This means that for each of the n elements, we perform approximately n comparisons in the worst case. Thus, the number of operations grows proportionally to n multiplied by n, resulting in approximately n * n operations. Simplifying this, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input array, comparing each element to every other element. It remembers, at most, two single numbers. The algorithm uses a fixed number of variables to track the current number being checked and the two single numbers, irrespective of the input size N. Therefore, the auxiliary space required does not depend on the input size, resulting in constant space complexity.

Optimal Solution

Approach

The goal is to find the two unique numbers in a list where all other numbers appear twice. The trick is to use bitwise operations to isolate the difference between the two unique numbers and then separate the numbers into two groups based on that difference.

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

First, combine all the numbers in the list using the 'exclusive or' operation, which gives you a single number that represents the combined difference between the two unique numbers.
Next, find the rightmost bit that is 'on' (equal to 1) in the combined difference. This bit tells you where the two unique numbers differ.
Now, go through the original list again. Separate the numbers into two groups: one group where the rightmost 'on' bit is also 'on', and another group where that bit is 'off'. The two unique numbers will end up in different groups.
Finally, in each group, combine all the numbers using the 'exclusive or' operation again. The result of each 'exclusive or' will be one of the unique numbers you were looking for.

Code Implementation

def single_number_iii(numbers):
    xor_sum = 0
    for number in numbers:
        xor_sum ^= number

    # Find the rightmost set bit
    rightmost_bit = xor_sum & -xor_sum

    number1 = 0
    number2 = 0

    # Divide numbers into two groups
    for number in numbers:
        if number & rightmost_bit:
            number1 ^= number
        else:
            number2 ^= number

    return [number1, number2]

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of size n three times. The first iteration performs XOR operations to find the XOR of the two unique numbers. The second iteration finds the rightmost set bit. The third iteration partitions the numbers into two groups and XORs them to find the two unique numbers. Each iteration performs a constant amount of work per element. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a few integer variables to store the XOR result, the rightmost set bit, and the two unique numbers. These variables consume a constant amount of memory regardless of the input array's size (N). Therefore, the auxiliary space used by the algorithm is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array because there are no single numbers to find.
Array with fewer than 2 elements	Return an empty array since there can't be two single numbers.
Array with exactly two distinct elements	The bit manipulation solution should correctly identify and return those two elements.
Array contains negative numbers, zeros, or very large positive/negative numbers	The bitwise XOR operations should work correctly with these number ranges within the typical integer limits.
Integer overflow during XOR operation when two extremely large numbers are XORed	The code should ideally use a data type capable of handling large numbers to avoid overflow, or implement overflow checks.
All numbers are the same except for the two single numbers	The XOR and bit masking operations will still isolate the two single numbers correctly.
Array contains only one unique number occurring twice	The result will be incorrect, the algorithm expects two unique numbers that appears once.
Large input array affecting time complexity	The bit manipulation solution scales linearly, O(n), so it should perform adequately even with large inputs.

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 for the integers in the input array? Can they be negative, zero, or very large?
Is it guaranteed that there will always be exactly two single numbers, and all other numbers appear exactly twice?
What should I return if the input array is null or empty?
Is the order of the two unique numbers in the output array significant, or can I return them in any order?
What is the maximum possible size of the input array, and should I be concerned about integer overflow during any calculations?

Brute Force Solution

Approach

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

Take the first number in the collection.
Compare this number to every other number in the collection.
If you find a match, it's not a single number, so move on to the next number.
If you compare it to every other number and don't find a match, remember this number.
Repeat this process for every number in the collection.
After checking all the numbers, you'll have identified the two numbers that appeared only once.

Code Implementation

def single_number_iii_brute_force(numbers):
    single_numbers = []
    for first_index in range(len(numbers)):
        is_single = True

        # Check if the current number is a duplicate
        for second_index in range(len(numbers)):
            if first_index != second_index and numbers[first_index] == numbers[second_index]:
                is_single = False
                break

        # Add to result if no duplicates found
        if is_single:
            single_numbers.append(numbers[first_index])

    return single_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, combine all the numbers in the list using the 'exclusive or' operation, which gives you a single number that represents the combined difference between the two unique numbers.
Next, find the rightmost bit that is 'on' (equal to 1) in the combined difference. This bit tells you where the two unique numbers differ.
Now, go through the original list again. Separate the numbers into two groups: one group where the rightmost 'on' bit is also 'on', and another group where that bit is 'off'. The two unique numbers will end up in different groups.
Finally, in each group, combine all the numbers using the 'exclusive or' operation again. The result of each 'exclusive or' will be one of the unique numbers you were looking for.

Code Implementation

def single_number_iii(numbers):
    xor_sum = 0
    for number in numbers:
        xor_sum ^= number

    # Find the rightmost set bit
    rightmost_bit = xor_sum & -xor_sum

    number1 = 0
    number2 = 0

    # Divide numbers into two groups
    for number in numbers:
        if number & rightmost_bit:
            number1 ^= number
        else:
            number2 ^= number

    return [number1, number2]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty array because there are no single numbers to find.
Array with fewer than 2 elements	Return an empty array since there can't be two single numbers.
Array with exactly two distinct elements	The bit manipulation solution should correctly identify and return those two elements.
Array contains negative numbers, zeros, or very large positive/negative numbers	The bitwise XOR operations should work correctly with these number ranges within the typical integer limits.
Integer overflow during XOR operation when two extremely large numbers are XORed	The code should ideally use a data type capable of handling large numbers to avoid overflow, or implement overflow checks.
All numbers are the same except for the two single numbers	The XOR and bit masking operations will still isolate the two single numbers correctly.
Array contains only one unique number occurring twice	The result will be incorrect, the algorithm expects two unique numbers that appears once.
Large input array affecting time complexity	The bit manipulation solution scales linearly, O(n), so it should perform adequately even with large inputs.