Sponsored
Sponsored
This approach uses the mathematical properties of numbers from 1 to n to determine the duplicate and missing numbers. Calculate the expected sum of numbers from 1 to n. Then, iterate through the array to find the actual sum of numbers and the sum of squares. By using these properties and equations, derive the duplicate and missing numbers.
Time Complexity: O(n), as we iterate through the input array three times.
Space Complexity: O(1), since we use a constant amount of space for variables.
1def findErrorNums(nums):
2 n = len(nums)
3 sum_n = n * (n + 1) // 2
4 sum_nums = sum(nums)
5 sum_square_n = n * (n + 1) * (2 * n + 1) // 6
6 sum_square_nums = sum(x * x for x in nums)
7 sum_diff = sum_n - sum_nums # missing - duplicate
8 square_sum_diff = sum_square_n - sum_square_nums # missing^2 - duplicate^2
9 sum_md = square_sum_diff // sum_diff # missing + duplicate
10 missing = (sum_md + sum_diff) // 2
11 duplicate = sum_md - missing
12 return [duplicate, missing]This Python function calculates the missing and duplicate numbers using the sum and difference method. It computes the total expected and actual sums, as well as the sums of squares. These computations help solving linear equations to find the exact missing and duplicate numbers.
In this approach, utilize a hashmap to count the occurrences of each number. Iterate over the numbers from 1 to n and use the occurrence count to identify the duplicated and missing numbers.
Time Complexity: O(n), where n is the length of nums, due to two iterations over the array.
Space Complexity: O(n), for storing the counts in a hashmap.
1import java.util.HashMap;
2import java
This Java solution uses a HashMap to keep track of the count of each number. As we iterate over the range, we check the frequency of each number to determine which is duplicated and which is missing.