Find First Missing Number In A Sequence Of Numbers
Solution 1:
How about this
var mynumbers = newArray(1,2,3,6,9,10);
var missing;
for(var i=1;i<=32;i++)
{
if(mynumbers[i-1] != i){
missing = i;
alert(missing);
break;
}
}
Solution 2:
The O(n) solutions are easy , but this is a common interview question and often we look for O(log n) time solution. Here is the javascript code. It's basically a modified binary search.
function misingNumInSeq(source, min = 0, max = source.length - 1){
if(min >= max){
return min + 1;
}
let pivot = Math.floor((min + max)/2);
// problem is in right side. Only look at right subarrayif(source[pivot] === pivot + 1){
return misingNumInSeq(source, pivot + 1, max);
} else {
return misingNumInSeq(source, min , pivot);
}
}
Output
misingNumInSeq([1,2,3,5,6,9,10,15])4
Solution 3:
By if(mynumbers[i] - mynumbers[i-1] != 1)
, you mean to say the series will always be incrementing by 1
?
var missing = (function (arr) {
var i;
for (i = 0; i < arr.length; ++i) {
if (i + arr[0] !== arr[i]) return i + arr[0];
}
if (i < 32) // if none missing inside array and not yet 32ndreturn i + arr[0]; // return next
}([1,2,3,6,9,10])); // 4alert(missing);
Solution 4:
You're going to need the break no matter what. That's what it's there for; to stop the loop from continuing on to the end. And you should use the length of the array instead of hardcoding 32 as the end condition, because your numbers only go up to 32, but there are possibly holes in the list so there will not be 32 elements in the array.
Since you know that each element should be 1 more than the previous element, then the number in the hole is clearly mynumbers[i - 1] + 1
.
var mynumbers = newArray(1,2,3,6,9,10);
for(var i = 1; i < mynumbers.length; i++) {
if(mynumbers[i] - mynumbers[i-1] != 1) {
alert("First missing number id: " + (mynumbers[i - 1] + 1));
break;
}
}
EDIT: This only holds true for the missing number not being 1. To catch that, you will need to check if (mynumbers[0] != 1)
Solution 5:
Edit:
functionfindFirstMissing(array) {
for (var i = 0; i < array.length; i++) {
if (i+1 !== array[i]) {
return i+1;
}
}
}
functionfindFirstMissing(array) {
for (var i = 0; i < array.length; i++) {
if (array[i+1] - array[i] !== 1) {
returnarray[i] + 1;
}
}
}
If you do it this way then storing it in a variable is easy:
var missing = findFirstMissing(array);
Post a Comment for "Find First Missing Number In A Sequence Of Numbers"