Find first missing number in a sequence of numbers

Question

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 ;-)

Fow what you are looking to achieve, You can combine the ideas in [this post](http://stackoverflow.com/questions/8273047/javascript-function-similar-to-python-range) and [this post](http://stackoverflow.com/a/5837541/1628832) — karthikr, Sep 17 '13 at 15:03

score 15 · Accepted Answer · answered Sep 17 '13 at 15:17

15

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;
   }
}

answered Sep 17 '13 at 15:17

Gowsikan

5,571
8
33
43

Actually... This was the most simple. Good job and thanks ;-) – Mansa Sep 17 '13 at 15:34
2

If somebody has given you this problem . He/she is definitely not looking for this solution. He probably looking for a more optimised solution. – sapy Mar 15 '17 at 07:44

sapy · Answer 2 · 2017-03-15T07:45:03.607

14

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

edited Mar 15 '17 at 07:45

answered Oct 16 '16 at 05:35

sapy

8,952
7
49
60

I'm not understanding why you are unnecessarily making the simple solution complex!. You can have a look at my answer. It's so easy and simple yet efficient though. – PHPLover Jul 31 '19 at 08:39
@PHPNut he literally explained it in the only sentence of the answer. It's a matter of complexity. O(log n) is better performance wise, that's good to know this kind of solution too. – johnnyBoy Jul 15 '22 at 18:47
this will give stack overflow for any 256 consecutive "occupied" values when "splitting" the search in pivoting chunks. The stack cannot go deeper than 255 on x86. – Marino Šimić Nov 26 '22 at 19:59

score 3 · Answer 3 · answered Sep 17 '13 at 15:07

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 32nd
        return i + arr[0]; // return next
}([1,2,3,6,9,10])); // 4
alert(missing);

answered Sep 17 '13 at 15:07

Paul S.

64,864
9
122
138

But if I remove the #1 it will still give me 4 as the first missing number? Shouldn't it be 1? – Mansa Sep 17 '13 at 15:14
If the sequence must begin `1`, replace all hardcoded `arr[0]` with `1`, I had assumed you were starting at an arbitrary number because your test was arbitrary. – Paul S. Sep 17 '13 at 19:16

jonhopkins · Answer 4 · 2013-09-17T15:15:38.153

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 = new Array(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)

Jeff Shaver · Answer 5 · 2013-09-17T15:32:05.190

1

Edit:

function findFirstMissing(array) {
    for (var i = 0; i < array.length; i++) {
        if (i+1 !== array[i]) {
            return i+1;
        }
    }
}

function findFirstMissing(array) {
    for (var i = 0; i < array.length; i++) {
        if (array[i+1] - array[i] !== 1) {
            return array[i] + 1;
        }
    }
}

If you do it this way then storing it in a variable is easy:

var missing = findFirstMissing(array);

edited Sep 17 '13 at 15:32

answered Sep 17 '13 at 15:07

Jeff Shaver

3,315
18
19

I like this, although same issue as the solution above. What if I remove the number 1... Shouldn't the first missing number be 1? – Mansa Sep 17 '13 at 15:17

score 1 · Answer 6 · answered Dec 25 '17 at 00:18

1

const firstNonConsecutive = arr => arr.find((el, i, arr) => (arr[i] - arr[i-1]) !== 1 && i !== 0)

this solution work for an array of positive numbers.

answered Dec 25 '17 at 00:18

tourniquet

1,375
2
15
19

Rahul Gaba · Answer 7 · 2018-04-13T12:10:57.987

A solution using array.reduce to find the first positive missing integer.

function solution(A) {
  return [...A].sort().reduce((acc, curr, i, arr) => {
    if (acc > curr) {
      arr.splice(1);
      return acc;
    }
    else if (arr[i + 1] - curr > 1 || arr.length === i + 1) {
      arr.splice(1);
      return curr + 1;
    }
    return acc;
  }, 1);
}

And here are few test cases:

console.log('solution([1, 3, 6, 4, 1, 2])',  solution([1, 3, 6, 4, 1, 2]) === 5)
console.log('solution([1, 3, 2, 8, 4])', solution([1, 3, 2, 8, 4]) === 5)
console.log('solution([1])', solution([1]) === 2)
console.log('solution([-1])', solution([-1]) === 1)
console.log('solution([0])', solution([0]) === 1)
console.log('solution([-1, -4, -5, -6, -190343])', solution([-1, -4, -5, -6, -190343]) === 1)

mjcconsulting · Answer 8 · 2019-07-31T07:40:24.717

Sometimes you just want simple if you know it's a small array:

let numbers = [1,2,3,6,9,10]
let m = 0

for (const i of numbers) if (i > ++m) break

console.log(m) // 4

Works if you remove 1 from start of array:

numbers = [2,3,6,9,10]
m = 0

for (const i of numbers) if (i > ++m) break

console.log(m) // 1

If the array can be contiguous, and if so you want the next highest number, then:

numbers = [1,2,3,4,5,6,7,8,9]
m = 0

for (const i of numbers) if (i > ++m) break
if (m == Math.max(...numbers)) m++

console.log(m) // 10

Short and sweet!

score 0 · Answer 9 · answered Mar 19 '21 at 20:26

//Find the missing number in a series
//output must be 12 in a table of 3 given in below series
let abc = [3, 6, 9, 15, 18, 21, 24];
var def = [],
  ghi = [];
for (var i = 1; i <= abc.length; i++) {
  if (i !== abc.length) {
    var diff = abc[i] - abc[i - 1];
    if (def.includes(diff) === false) {
      def.push(diff);
    } else {
      ghi.push(diff);
    }
  }
}

var finalArr = [];
if (ghi.length > def.length) finalArr = ghi;
else finalArr = def;
var finaldiff = finalArr[0];
var finalVal = abc.find((e, i) => {
  if (e !== abc.length) {
    var diff = abc[i] - abc[i - 1];
    return diff > finaldiff;
  }
})

console.log(finalVal - diff);

score -1 · Answer 10 · answered Sep 17 '13 at 15:05

for(var i = 1; i < mynumbers.length; i++) {
    if(mynumbers[i] - mynumbers[i-1] != 1) {
        alert("First missing number id: "+mynumbers[i-1]+1);
        i = mynumbers.length; // Replace the break
    }
}

If you want you can add an initial check : if (mynumbers[0] != 1) { ... }

PHPLover · Answer 11 · 2019-07-31T08:34:15.240

I think this is the simplest and optimum form of just a 2-step solution.

I think no better solution can be possible for this problem than this one.

This code uses minimum no. of variables, loops, conditionals, built-in functions and all the shitty, sloppy, unnecessary code.

This code can handle array of any length.

var mynumbers = new Array(76,77,78,79,80,81,82,83,84,125);

if(mynumbers.length > 1) {

  for(var i=0; i<=mynumbers.length-1; i++) {

    if(mynumbers[i+1] - 1 !== mynumbers[i]) { 

      alert("First Missing Term is : "+parseInt(mynumbers[i]+1));
      break;
    }

  }

}

Find first missing number in a sequence of numbers

11 Answers11

Linked

Related