Jobs

Interviews

Discussions

Set Mismatch #2 Most Asked

Easy

GitHub

2 views

Topics:

ArraysBit Manipulation

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

2 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Try coding it in LeetCode

Set Mismatch #2 Most Asked

Easy

GitHub

2 views

Topics:

ArraysBit Manipulation

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

2 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

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 expected range of numbers within the input array 'nums'? Could the numbers be negative, zero, or include very large positive values?
Is it guaranteed that the input array 'nums' will always have a length of n, where the numbers are expected to be in the range [1, n]?
If there are multiple possibilities for the duplicate and missing number, does the order in which I return them matter? Should the duplicate come first?
If the array is empty or null, how should I handle it? Should I return null or throw an exception?
Is it guaranteed that there will always be exactly one duplicate and one missing number in the array, or could there be cases where there are no duplicates/missing numbers?

Brute Force Solution

Approach

The problem involves finding a number that is both duplicated and missing from a sequence of numbers. The brute force strategy is all about checking every possible number and seeing if it fits the required conditions.

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

First, pick a number from the input to guess as the duplicate.
Next, count how many times that number appears in the input.
If the number appears more than once, confirm it's actually the duplicate. If it doesn't appear more than once, we didn't guess the right duplicate, so move on to the next number.
Now, find the number that is missing by going through each number within the expected range.
Check to see if that number is in the input.
If the number is not in the input, then it's the missing number.
If the number IS in the input, try the next number in the expected range to see if it's missing.
Once both the duplicate and missing numbers are confirmed, the answer is found.

Code Implementation

def find_error_numbers_brute_force(numbers):
    list_length = len(numbers)

    for possible_duplicate in numbers:
        duplicate_count = 0

        for number in numbers:
            if number == possible_duplicate:
                duplicate_count += 1

        # Confirm we found a duplicate before proceeding
        if duplicate_count > 1:

            duplicate_number = possible_duplicate

            for possible_missing in range(1, list_length + 1):
                is_missing = True

                for number in numbers:
                    if number == possible_missing:
                        is_missing = False
                        break

                # We found the missing number
                if is_missing:

                    missing_number = possible_missing
                    return [duplicate_number, missing_number]

    return []

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array to guess a duplicate. For each guess, it iterates through the array again to count its occurrences, taking O(n) time. After finding the duplicate, the algorithm iterates from 1 to n to find the missing number, and for each number, it scans the input array (up to n elements) to check for its presence. Therefore, the total time complexity is driven by nested loops, resulting in O(n * n) to find the duplicate and, in the worst case, O(n * n) to find the missing number, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through the input array 'nums', represented by N, to find the duplicate and missing numbers. It uses a few constant space variables like counters for occurrences and potentially a boolean to mark if a number is present. No auxiliary data structures like hash maps or arrays are created that scale with the input size. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The problem asks us to find a missing number and a duplicate number in a set that's supposed to contain consecutive numbers. The optimal approach involves using the expected sum and the expected sum of squares to quickly deduce the missing and duplicate numbers without searching the whole set repeatedly.

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

Calculate the expected sum of all the numbers if the set were complete (from 1 to the size of the set).
Calculate the actual sum of the numbers currently in the set.
The difference between the expected sum and the actual sum gives you one key piece of information: the difference between the missing number and the duplicate number.
Calculate the expected sum of the squares of all the numbers if the set were complete.
Calculate the actual sum of the squares of the numbers currently in the set.
The difference between the expected sum of squares and the actual sum of squares gives you another key piece of information related to the missing and duplicate numbers.
Using the two pieces of information you calculated (from the sums and sums of squares), solve the two equations for two unknowns (the missing and duplicate numbers). This will directly give you the answer.

Code Implementation

def find_error_nums(nums):
    array_length = len(nums)

    expected_sum = array_length * (array_length + 1) // 2
    actual_sum = sum(nums)

    expected_sum_of_squares = array_length * (array_length + 1) * (2 * array_length + 1) // 6
    actual_sum_of_squares = sum(number * number for number in nums)

    # Calculate the difference between the sums and the sums of squares.
    difference_of_sums = expected_sum - actual_sum
    difference_of_squares = expected_sum_of_squares - actual_sum_of_squares

    # Use these differences to solve for duplicate_number and missing_number.
    sum_of_numbers = difference_of_squares // difference_of_sums
    duplicate_number = (sum_of_numbers - difference_of_sums) // 2

    # Solving for missing_number.
    missing_number = sum_of_numbers - duplicate_number

    return [duplicate_number, missing_number]

Big(O) Analysis

Time Complexity

O(n) – The algorithm calculates the expected sum and sum of squares in constant time based on the input size n. It then iterates through the input array of size n once to calculate the actual sum and sum of squares. Finally, it solves a system of two equations with two unknowns, which takes constant time. Thus, the dominant operation is iterating through the array once, resulting in a time complexity of O(n).

Space Complexity

O(1) – The described algorithm calculates expected and actual sums and sums of squares. It only uses a few variables to store intermediate calculations like the expected sum, actual sum, expected sum of squares, and actual sum of squares, as well as the duplicate and missing numbers. The number of such variables is fixed and independent of the input array's size, N. Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.
Input array with a single element	Return the array with the single element repeated as the duplicate and 0 as the missing value.
Input array with all elements identical	The repeating number is the element and the missing number is one more than the element (or 1 if the element is n).
Large input array potentially causing integer overflow when calculating the sum or expected sum	Use long data type to store the sums to prevent overflow.
The missing number is the last number in the range [1, n]	The algorithm correctly identifies the last number as missing when not found in the array.
The duplicate number is the first number in the range [1, n]	The algorithm correctly identifies the first number as duplicated if present multiple times.
The input array contains very large numbers	If the prompt defines a reasonable upper bound for inputs then handle normally, otherwise consider scaling and representation issues.
Input array is already in sorted order	The algorithm must function correctly regardless of the input array's initial order.

Null or empty input array

How to Handle:

Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.

Input array with a single element

How to Handle:

Return the array with the single element repeated as the duplicate and 0 as the missing value.

Input array with all elements identical

How to Handle:

The repeating number is the element and the missing number is one more than the element (or 1 if the element is n).

Large input array potentially causing integer overflow when calculating the sum or expected sum

How to Handle:

Use long data type to store the sums to prevent overflow.

The missing number is the last number in the range [1, n]

How to Handle:

The algorithm correctly identifies the last number as missing when not found in the array.

The duplicate number is the first number in the range [1, n]

How to Handle:

The algorithm correctly identifies the first number as duplicated if present multiple times.

The input array contains very large numbers

How to Handle:

If the prompt defines a reasonable upper bound for inputs then handle normally, otherwise consider scaling and representation issues.

Input array is already in sorted order

How to Handle:

The algorithm must function correctly regardless of the input array's initial order.

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 expected range of numbers within the input array 'nums'? Could the numbers be negative, zero, or include very large positive values?
Is it guaranteed that the input array 'nums' will always have a length of n, where the numbers are expected to be in the range [1, n]?
If there are multiple possibilities for the duplicate and missing number, does the order in which I return them matter? Should the duplicate come first?
If the array is empty or null, how should I handle it? Should I return null or throw an exception?
Is it guaranteed that there will always be exactly one duplicate and one missing number in the array, or could there be cases where there are no duplicates/missing numbers?

Brute Force Solution

Approach

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

First, pick a number from the input to guess as the duplicate.
Next, count how many times that number appears in the input.
If the number appears more than once, confirm it's actually the duplicate. If it doesn't appear more than once, we didn't guess the right duplicate, so move on to the next number.
Now, find the number that is missing by going through each number within the expected range.
Check to see if that number is in the input.
If the number is not in the input, then it's the missing number.
If the number IS in the input, try the next number in the expected range to see if it's missing.
Once both the duplicate and missing numbers are confirmed, the answer is found.

Code Implementation

def find_error_numbers_brute_force(numbers):
    list_length = len(numbers)

    for possible_duplicate in numbers:
        duplicate_count = 0

        for number in numbers:
            if number == possible_duplicate:
                duplicate_count += 1

        # Confirm we found a duplicate before proceeding
        if duplicate_count > 1:

            duplicate_number = possible_duplicate

            for possible_missing in range(1, list_length + 1):
                is_missing = True

                for number in numbers:
                    if number == possible_missing:
                        is_missing = False
                        break

                # We found the missing number
                if is_missing:

                    missing_number = possible_missing
                    return [duplicate_number, missing_number]

    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Calculate the expected sum of all the numbers if the set were complete (from 1 to the size of the set).
Calculate the actual sum of the numbers currently in the set.
The difference between the expected sum and the actual sum gives you one key piece of information: the difference between the missing number and the duplicate number.
Calculate the expected sum of the squares of all the numbers if the set were complete.
Calculate the actual sum of the squares of the numbers currently in the set.
The difference between the expected sum of squares and the actual sum of squares gives you another key piece of information related to the missing and duplicate numbers.
Using the two pieces of information you calculated (from the sums and sums of squares), solve the two equations for two unknowns (the missing and duplicate numbers). This will directly give you the answer.

Code Implementation

def find_error_nums(nums):
    array_length = len(nums)

    expected_sum = array_length * (array_length + 1) // 2
    actual_sum = sum(nums)

    expected_sum_of_squares = array_length * (array_length + 1) * (2 * array_length + 1) // 6
    actual_sum_of_squares = sum(number * number for number in nums)

    # Calculate the difference between the sums and the sums of squares.
    difference_of_sums = expected_sum - actual_sum
    difference_of_squares = expected_sum_of_squares - actual_sum_of_squares

    # Use these differences to solve for duplicate_number and missing_number.
    sum_of_numbers = difference_of_squares // difference_of_sums
    duplicate_number = (sum_of_numbers - difference_of_sums) // 2

    # Solving for missing_number.
    missing_number = sum_of_numbers - duplicate_number

    return [duplicate_number, missing_number]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.
Input array with a single element	Return the array with the single element repeated as the duplicate and 0 as the missing value.
Input array with all elements identical	The repeating number is the element and the missing number is one more than the element (or 1 if the element is n).
Large input array potentially causing integer overflow when calculating the sum or expected sum	Use long data type to store the sums to prevent overflow.
The missing number is the last number in the range [1, n]	The algorithm correctly identifies the last number as missing when not found in the array.
The duplicate number is the first number in the range [1, n]	The algorithm correctly identifies the first number as duplicated if present multiple times.
The input array contains very large numbers	If the prompt defines a reasonable upper bound for inputs then handle normally, otherwise consider scaling and representation issues.
Input array is already in sorted order	The algorithm must function correctly regardless of the input array's initial order.

Null or empty input array

How to Handle:

Return an empty array or throw an IllegalArgumentException as appropriate for invalid input.

Input array with a single element

How to Handle:

Return the array with the single element repeated as the duplicate and 0 as the missing value.

Input array with all elements identical

How to Handle:

The repeating number is the element and the missing number is one more than the element (or 1 if the element is n).

Large input array potentially causing integer overflow when calculating the sum or expected sum

How to Handle:

Use long data type to store the sums to prevent overflow.

The missing number is the last number in the range [1, n]

How to Handle:

The algorithm correctly identifies the last number as missing when not found in the array.

The duplicate number is the first number in the range [1, n]

How to Handle:

The algorithm correctly identifies the first number as duplicated if present multiple times.

The input array contains very large numbers

How to Handle:

If the prompt defines a reasonable upper bound for inputs then handle normally, otherwise consider scaling and representation issues.

Input array is already in sorted order

How to Handle:

The algorithm must function correctly regardless of the input array's initial order.

0/0 GitHub questions completed

0/0 completed