Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find first missing number in a sequence of numbers

I am trying to figure out how to find the first missing number of a sequence of numbers like this (1,2,3,5,6,9,10,15)

I want to put the first missing number, #4, into an variable for later use but don't know how to do so?

I have tried this but this only gives me the last number:

var mynumbers=new Array(1,2,3,6,9,10);
for(var i = 1; i < 32; i++) {
    if(mynumbers[i] - mynumbers[i-1] != 1) {
        alert("First missing number id: "+mynumbers[i]);
        break;
    }
}

First of all it gives me the first number after an "hole" in the numbersequence, secondly it continues to alert all numbers comming after an "hole" if I don't insert an break. I only want the first missing number of an numbersequence from 1 - 32. How do i do so?

Hoping for help and thanks in advance ;-)

like image 443
Mansa Avatar asked Sep 17 '13 14:09

Mansa


3 Answers

How about this

var mynumbers = new Array(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;
   }
}
like image 92
Gowsikan Avatar answered Oct 21 '22 06:10

Gowsikan


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 sub array
    if(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
like image 44
sapy Avatar answered Oct 21 '22 05:10

sapy


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 32nd
        return i + arr[0]; // return next
}([1,2,3,6,9,10])); // 4
alert(missing);
like image 41
Paul S. Avatar answered Oct 21 '22 05:10

Paul S.