Finding repeating and missing numbers Using Hashing
We use hashstore the count every element from the 1 to N range. We store the count of every element by traversing the whole array. We will return the repeating number which has a count of 2 in the hash array, and return the missing number which has a count of 0.
Example: This JavaScript code employs a hash array to efficiently find the repeating and missing numbers within an array, providing a concise and straightforward solution.
Javascript
function MissingandRepeatingNumbers(vec) { const n = vec.length; const hash = new Array(n + 1).fill(0); // store count of every element in hash array for (let i = 0; i < n; i++) { hash[vec[i]]++; } // Find the repeating and missing number: let repeating = -1, missing = -1; for (let i = 1; i <= n; i++) { if (hash[i] === 2) repeating = i; else if (hash[i] === 0) missing = i; if (repeating !== -1 && missing !== -1) break ; } return [repeating, missing]; } const vec = [3, 1, 2, 5, 4, 6, 7, 5]; const ans = MissingandRepeatingNumbers(vec); console.log( "The repeating and missing numbers are {" + ans[0] + ", " + ans[1] + "}" ); |
The repeating and missing numbers are {5, 8}
Time Complexity: O(2n), as we are using two loops iterations.
Space Complexity: O(n), as we are using hash array.
Find the Repeating & Missing Numbers in JavaScript Array ?
JavaScript allows us to find the repeating and missing number in a given array which includes numbers from 1 to N range. We are given an array that has numbers present from 1 to N range, where N is any natural number. One number is present two times and one number is missing from the range.
We have to return these numbers which can be achieved by several methods using JavaScript which are as follows:
Table of Content
- Using array manipulation
- Using Hashing
Contact Us