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.
1using System.Collections.Generic;
2
3public class Solution {
4 public int[] FindErrorNums(int[] nums) {
5 Dictionary<int, int> countMap = new Dictionary<int, int>();
foreach (var num in nums) {
if (countMap.ContainsKey(num))
countMap[num]++;
else
countMap[num] = 1;
}
int duplicate = -1, missing = -1;
for (int i = 1; i <= nums.Length; i++) {
if (countMap.ContainsKey(i)) {
if (countMap[i] == 2) duplicate = i;
} else {
missing = i;
}
}
return new int[] { duplicate, missing };
}
}This C# solution also uses a dictionary to track occurrences of numbers. Similar to the Java solution, it checks the presence and count of each number.