algoadvance

Leetcode 645. Set Mismatch

Problem Statement

You are given an integer array nums representing the data collected from a survey where the numbers come from the range 1 to n. One number is missing, and one number is duplicated.

Return an array {dup, missing}:

  1. dup is the number that appears twice.
  2. missing is the number that is missing from the array.

Clarifying Questions

  1. What is the length of nums?
    • The length of nums is n, which corresponds to the largest number that should be present.
  2. Can there be any repeat elements other than the duplicated issue stated?
    • No, there is exactly one number that appears twice and exactly one number that is missing.
  3. Are there any constraints on the values in nums?
    • The values are supposed to be within the range from 1 to n.

Strategy

To solve this problem, we’ll follow these steps:

  1. Use an array to keep track of the counts of each number.
  2. Iterate through the input array and populate the count array.
  3. Identify the duplicated and the missing numbers by checking the count array.

Alternatively, we can use a more optimal approach (both time and space complexity wise) by leveraging mathematical properties:

  1. Calculate the expected sum of numbers from 1 to n and the sum of squares for the range.
  2. Calculate the actual sum and sum of squares from the given array nums.
  3. Use the difference between the expected and actual sums of values and squares to determine the duplicated and missing numbers.

We’ll follow this optimal mathematical approach for our solution.

Code

#include <vector>
#include <cmath>

std::vector<int> findErrorNums(std::vector<int>& nums) {
    int len = nums.size();
    long long expected_sum = (len * (len + 1)) / 2;
    long long expected_sum_squares = (len * (len + 1) * (2 * len + 1)) / 6;

    long long actual_sum = 0;
    long long actual_sum_squares = 0;

    for (int num : nums) {
        actual_sum += num;
        actual_sum_squares += (long long)num * num;
    }

    long long diff_sum = expected_sum - actual_sum;                      // missing - duplicate
    long long diff_sum_squares = expected_sum_squares - actual_sum_squares;  // missing^2 - duplicate^2

    long long sum_miss_dup = diff_sum_squares / diff_sum;                // missing + duplicate

    int missing = (diff_sum + sum_miss_dup) / 2;
    int duplicate = sum_miss_dup - missing;

    return {duplicate, missing};
}

Explanation

  1. Calculations:
    • expected_sum: Sum of numbers 1 to n.
    • expected_sum_squares: Sum of squares of numbers 1 to n.
    • actual_sum: Sum of the given array nums.
    • actual_sum_squares: Sum of squares of the numbers in nums.
  2. Differences:
    • diff_sum: This yields missing - duplicate.
    • diff_sum_squares: This yields missing^2 - duplicate^2.
  3. Equations Derived:
    • Sum relation: missing + duplicate = diff_sum_squares / diff_sum.
  4. Solving:
    • Using the two equations (difference and sum relation), solve for missing and duplicate.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI