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.
1function findErrorNums(nums) {
2 const n = nums.length;
3 const sumN = n * (n + 1) / 2;
4 const sumNum = nums.reduce((a, b) => a + b, 0);
5 const sumSquareN = n * (n + 1) * (2 * n + 1) / 6;
6 const sumSquareNum = nums.reduce((a, b) => a + b * b, 0);
7 const sumDiff = sumN - sumNum;
8 const squareSumDiff = sumSquareN - sumSquareNum;
9 const sumMD = squareSumDiff / sumDiff;
10 const missing = (sumMD + sumDiff) / 2;
11 const duplicate = sumMD - missing;
12 return [duplicate, missing];
13}This JavaScript function follows the same line of reasoning as the Python solution. It calculates the difference of sums and sums of squares, then derives the missing and duplicate values.
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
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.