Jobs

Interviews

Discussions

Single Number

Easy

Palantir

2 views

Topics:

ArraysBit Manipulation

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 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

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

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Single Number

Easy

Palantir

2 views

Topics:

ArraysBit Manipulation

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 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

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

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

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:

Can the input array contain negative numbers or zero?
What is the range of values within the `nums` array?
Is it guaranteed that there will always be exactly one number that appears only once, or should I handle cases where all numbers appear twice or no number appears only once?
What is the maximum possible size of the input array `nums`?
Are we concerned about space complexity, or is minimizing time complexity the primary goal?

Brute Force Solution

Approach

The brute force approach to finding the single number involves checking each number in the list against all the other numbers. We try to find a match for each number, and the one that doesn't have a match is the single number.

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

Take the first number from the list.
Compare it to all the other numbers in the list.
If you find an exact match (another number that's the same), move on to the next number in the list.
If you go through the entire list and don't find a match for the current number, then this number is the single number.
If you found a match, repeat the process with the next number in the list until you find the single number that has no match.

Code Implementation

def find_single_number_brute_force(numbers):
    for current_number_index in range(len(numbers)):
        current_number = numbers[current_number_index]
        found_match = False

        # Compare current number to the others
        for other_number_index in range(len(numbers)):
            # Don't compare the number to itself
            if current_number_index != other_number_index:
                other_number = numbers[other_number_index]

                if current_number == other_number:
                    found_match = True

                    # Move to next number if we found a match
                    break

        # Return the number if no match was found
        if not found_match:

            # The current number is the single number
            return current_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force algorithm iterates through each of the n numbers in the input array. For each number, it then iterates through almost all the other numbers in the array to find a match. In the worst case, for each of the n numbers, we might perform close to n comparisons. Therefore, the total number of operations approximates n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through the input list to find a single number without using any auxiliary data structures. The algorithm only uses a few variables for comparisons and indexing, such as the current number and its potential matches. These variables take up constant space regardless of the input list's size, N, where N is the number of elements in the list. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks to find the unique number in a list where every other number appears exactly twice. The clever approach leverages a mathematical trick to efficiently identify the single number without needing to count occurrences or compare every pair. It uses the properties of a special operation.

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

Imagine you have a magic box. If you put a number into it twice, they disappear. If you put a number in only once, it remains.
Start with nothing in the magic box.
Take each number from the list, one by one, and put it into the magic box.
After putting all the numbers into the magic box, the only number remaining inside is the one that appeared only once.

Code Implementation

def find_single_number(numbers):
    single_number = 0

    # Use XOR to find the single number.
    for number in numbers:

        # XOR operation cancels out pairs.
        single_number ^= number

    #The remaining value is the single number
    return single_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n numbers in the input list nums exactly once. For each number, it performs a constant-time operation (the XOR operation). Therefore, the overall time complexity is directly proportional to the number of elements in the list. This results in a linear time complexity of O(n).

Space Complexity

O(1) – The provided plain English explanation describes a process that operates in place, using only the 'magic box' analogy to illustrate the algorithm's logic. The 'magic box' doesn't represent an actual data structure that grows with the input size N (where N is the number of elements in the list). Therefore, no additional data structures are allocated. Consequently, the auxiliary space complexity is constant, independent of the input size.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an exception, depending on problem specifications, as there is no single number in an empty array.
Array with only one element	Return the single element directly, as it is trivially the single number.
Array with maximum allowed size (considering memory constraints)	Ensure the chosen algorithm (e.g., XOR) has acceptable time and space complexity for large inputs; avoid memory-intensive solutions like large hash maps.
All elements are the same (invalid input according to the problem description)	The XOR solution would return the repeating element; the hashmap solution would not populate, so a 0 (if returned) or error might be needed to indicate a violation of constraints.
Array contains negative numbers, zero, and positive numbers	XOR solution handles all these cases directly; Hash map solution handles all these cases without modification.
Integer overflow with XOR operation (if numbers are very large)	Consider using a language with arbitrary-precision integers or check for overflow conditions if the XOR operation might exceed integer limits.
Array contains the maximum possible integer value	The XOR solution handles this correctly; hashmap needs to accommodate this without memory overflow.
Highly skewed distribution with a large range of numbers	XOR solution still works efficiently; hash map needs to scale efficiently in terms of hash function and memory usage.

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:

Can the input array contain negative numbers or zero?
What is the range of values within the `nums` array?
Is it guaranteed that there will always be exactly one number that appears only once, or should I handle cases where all numbers appear twice or no number appears only once?
What is the maximum possible size of the input array `nums`?
Are we concerned about space complexity, or is minimizing time complexity the primary goal?

Brute Force Solution

Approach

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

Take the first number from the list.
Compare it to all the other numbers in the list.
If you find an exact match (another number that's the same), move on to the next number in the list.
If you go through the entire list and don't find a match for the current number, then this number is the single number.
If you found a match, repeat the process with the next number in the list until you find the single number that has no match.

Code Implementation

def find_single_number_brute_force(numbers):
    for current_number_index in range(len(numbers)):
        current_number = numbers[current_number_index]
        found_match = False

        # Compare current number to the others
        for other_number_index in range(len(numbers)):
            # Don't compare the number to itself
            if current_number_index != other_number_index:
                other_number = numbers[other_number_index]

                if current_number == other_number:
                    found_match = True

                    # Move to next number if we found a match
                    break

        # Return the number if no match was found
        if not found_match:

            # The current number is the single number
            return current_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a magic box. If you put a number into it twice, they disappear. If you put a number in only once, it remains.
Start with nothing in the magic box.
Take each number from the list, one by one, and put it into the magic box.
After putting all the numbers into the magic box, the only number remaining inside is the one that appeared only once.

Code Implementation

def find_single_number(numbers):
    single_number = 0

    # Use XOR to find the single number.
    for number in numbers:

        # XOR operation cancels out pairs.
        single_number ^= number

    #The remaining value is the single number
    return single_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an exception, depending on problem specifications, as there is no single number in an empty array.
Array with only one element	Return the single element directly, as it is trivially the single number.
Array with maximum allowed size (considering memory constraints)	Ensure the chosen algorithm (e.g., XOR) has acceptable time and space complexity for large inputs; avoid memory-intensive solutions like large hash maps.
All elements are the same (invalid input according to the problem description)	The XOR solution would return the repeating element; the hashmap solution would not populate, so a 0 (if returned) or error might be needed to indicate a violation of constraints.
Array contains negative numbers, zero, and positive numbers	XOR solution handles all these cases directly; Hash map solution handles all these cases without modification.
Integer overflow with XOR operation (if numbers are very large)	Consider using a language with arbitrary-precision integers or check for overflow conditions if the XOR operation might exceed integer limits.
Array contains the maximum possible integer value	The XOR solution handles this correctly; hashmap needs to accommodate this without memory overflow.
Highly skewed distribution with a large range of numbers	XOR solution still works efficiently; hash map needs to scale efficiently in terms of hash function and memory usage.