algoadvance

Leetcode 2965. Find Missing and Repeated Values

Problem Statement

You are given an array nums containing n integers where the integers are in the range [1, n]. One number appears once (missing number) and another number appears twice (repeated number). Your task is to find these two numbers.

Clarifying Questions

1. Input Size: What is the typical size of the array nums we should expect?
2. Range of Values: Are the values in the array strictly within the range [1, n]?
3. Output Format: Should the result be returned as a vector/array or is any other format acceptable?

Assuming it’s a typical LeetCode medium level problem:

• The array size n can be at most (10^4).
• The values are guaranteed to be within the range [1, n].
• Return the result as a vector of integers in C++.

Strategy

We need to solve two parts of the problem: identifying the missing number and the repeated number. Let’s utilize the properties of the sum and squared sum of the first n natural numbers for this.

1. Sum Property:
   • Sum of the first n natural numbers: ( S = \frac{n(n + 1)}{2} )
   • Sum of the squares of the first n natural numbers: ( P = \frac{n(n + 1)(2n + 1)}{6} )
2. Given the array nums:
   • Let sum(nums) be the sum of elements in the array.
   • Let sum(nums^2) be the sum of the squares of elements in the array.
3. Equations:
   • ( \text{repeated} - \text{missing} = \text{sum(nums)} - S )
   • ( \text{repeated}^2 - \text{missing}^2 = \text{sum(nums^2)} - P )
   • This simplifies to ( (\text{repeated} + \text{missing}) \times (\text{repeated} - \text{missing}) = \text{sum(nums^2)} - P )

By solving these equations, we can find the repeated and missing values.

Code

#include <vector>
#include <iostream>
using namespace std;

vector<int> findErrorNums(vector<int>& nums) {
    long long n = nums.size();
    long long sum_n = n * (n + 1) / 2;
    long long sum_n2 = n * (n + 1) * (2 * n + 1) / 6;

    long long sum_nums = 0, sum_nums2 = 0;
    for (int num : nums) {
        sum_nums += num;
        sum_nums2 += (long long)num * num;
    }

    long long diff = sum_nums - sum_n; // repeated - missing
    long long sq_diff = sum_nums2 - sum_n2; // repeated^2 - missing^2

    // Solving the equations:
    // repeated + missing = sq_diff / diff
    long long sum = sq_diff / diff;

    int repeated = (diff + sum) / 2;
    int missing = sum - repeated;

    return {repeated, missing};
}

int main() {
    vector<int> nums = {1, 2, 2, 4};
    vector<int> result = findErrorNums(nums);
    cout << "Repeated: " << result[0] << ", Missing: " << result[1] << endl;
    return 0;
}

Time Complexity

• Time Complexity: (O(n))
  • We iterate over the array to calculate the sums and the squared sums which takes linear time.
• Space Complexity: (O(1))
  • We use a constant amount of extra space for storing the sums and differences.

This method leverages mathematical properties and is efficient for the given problem constraints.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?