Find missing numbers in array

Question

I'm trying to find each missing number in an array like the following.

Array ( 
  [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 8 
  [8] => 9 [9] => 10 [10] => 11 [11] => 12 [12] => 13 [13] => 14 [14] => 15 
  [15] => 16 [16] => 17 [17] => 18 [18] => 19 [19] => 20 [20] => 21 [21] => 22 
  [22] => 23 [23] => 24 [24] => 25 [25] => 26 [26] => 27 [27] => 28 [28] => 29 
  [29] => 30 [30] => 31 [31] => 32 [32] => 33 [33] => 34 [34] => 35 [35] => 36 
  [36] => 37 [37] => 38 [38] => 39 [39] => 40 [40] => 41 [41] => 42 [42] => 43 
  [43] => 44 [44] => 45 [45] => 46 [46] => 47 [47] => 48 [48] => 49 [49] => 50 
  [50] => 51 [51] => 52 [52] => 53 [53] => 54 [54] => 55 [55] => 56 [56] => 57 
  [57] => 58 [58] => 59 [59] => 60 [60] => 61 [61] => 62 [62] => 63 [63] => 64 
  [64] => 67 [65] => 68 [66] => 69 
)

The numbers 65,66 are missing in this particular array.

My question how do I figure out which numbers are missing with the help of PHP. Specifically what I need to find out is the lowest missing number.

Why: Because then I can assign that number to a member as an id.

I don't think that's the best way to get a unique id - what happens when you have 100000000 users? Might take a while to find the id. — Jeff Foster
– Jeff Foster, Commented Nov 12, 2010 at 9:28
@Jeff Foster, if at any time it takes a long time to find the id, the obvious solution is to delete users where id > 1000;. It will be fast again! :) — acm
– acm, Commented Nov 12, 2010 at 10:07

codaddict · Accepted Answer · 2010-11-12 09:33:22Z

70

You can make use of array_diff and range functions as:

// given array. 3 and 6 are missing.
$arr1 = array(1,2,4,5,7); 

// construct a new array:1,2....max(given array).
$arr2 = range(1,max($arr1));                                                    

// use array_diff to get the missing elements 
$missing = array_diff($arr2,$arr1); // (3,6)

answered Nov 12, 2010 at 9:33

codaddict

457k83 gold badges501 silver badges537 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Hristian Yordanov Over a year ago

If you have leading zero in the array it does not works

emurano · Accepted Answer · 2010-11-12 09:36:05Z

7

I'm assuming the number is the element, not the key, of the array. I'm also assuming that the numbers start from 1, not 0.

$Expected = 1;
foreach ($InputArray as $Key => $Number)
{
   if ($Expected != $Number)
   {
       break;
   }
   $Expected++;
}

echo $Number;

answered Nov 12, 2010 at 9:36

emurano

9736 silver badges15 bronze badges

1 Comment

Jarnail S Over a year ago

I like this because you are not using any function. Good one

Toon Krijthe · Accepted Answer · 2012-12-03 16:35:06Z

5

For big sorted arrays of unique numbers, you can binary search the array for either the lowest or highest unused number. Cost=Log2N. Example: 65536 items can be searched in 16 loops since

if ( arr[hi] - arr[lo] > hi - lo )
  ... there are unused numbers in that range ...

So (I don't know PHP, but it can be translated...):

lo = first entry index
hi = last entry index
if ( arr[hi] - arr[lo] == hi - lo )
  return arr[hi]+1; // no gaps so return highest + 1
do
  {
  mid = (lo + hi) / 2;
  if ( arr[mid] - arr[lo] > mid - lo )   // there is a gap in the bottom half somewhere
    hi = mid; // search the bottom half
  else
    lo = mid; // search the top half
  } while ( hi > lo + 1 ); // search until 2 left
return arr[lo]+1;

edited Dec 3, 2012 at 16:35

Toon Krijthe

53.6k38 gold badges151 silver badges204 bronze badges

answered Dec 28, 2010 at 17:27

user556202

512 bronze badges

Comments

Asheesh Kumar Singh · Accepted Answer · 2018-07-11 20:58:35Z

If given input is not in sorted order and size of input is very large then we can use following logic in any programming language:

Algorithm

bring smaller chunk into memory from large input
initialize three variables say min = 0, max = 0 and missingIds = []
scan smaller chunked input from left to right
1. if scannedValue found in missingIds then, pop scannedValue from missingIds go to next value;
2. If scanned value is near to min then, find all the missing numbers between scannedValue and min, push into missingIds
  
  min = scannedValue;
3. Else if scanned value is near to max then, find all the missing numbers between scannedValue and max, push into missingIds
  
  max = scannedValue;
repeat above steps until large input scanned from left to right

Example in PHP

<?php
$largeInput = [40,41,42,43,44,45,1,2,3,4,5,6,7,8,9,10,11,12,13,14,35,36,37,38,39,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,67,68,69,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34];
$missingIds = [];
$min = 0;
$max = 0;
$chunkSize = 10;
$chunkNo = 0;
$currentInput = array_slice($largeInput, $chunkNo, $chunkSize);
while(count($currentInput) > 0) {
    foreach($currentInput as $id) {
        if(in_array($id,$missingIds)) {
            $missingIds = array_diff($missingIds,[$id]);
            continue;
        }
        if($id <= $min) {
            $distMin = $min - $id;
            if($distMin > 2) {
                $tempArr = range($id+1,$min-1);
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } else if ($distMin > 1) {
                $tempArr = [$id+1];
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } 
            $min = $id;
        } else if ($id >= $max){
            $distMax = $id - $max;
            if($distMax > 2) {
                $tempArr = range($max+1,$id-1);
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } else if ($distMax > 1) {
                $tempArr = [$max+1];
                $missingIds = array_merge($missingIds, $tempArr);
                $tempArr = [];
            } 
            $max = $id;
        }   
    }
    $chunkNo++;
    $currentInput = array_slice($largeInput, $chunkNo, $chunkSize);
}
print_r($missingIds);

David Newcomb · Accepted Answer · 2010-11-12 11:50:29Z

2

//$idArrayMissing = array([0] => 1, [1] => 2, [2] => 4, [3] => 5, [4] => 6, [5] => 7);
$idArrayMissing = array(1, 2, 4, 5, 6, 7);

//$idArrayFull = array([0] => 1, [1] => 2, [2] => 3, [3] => 4, [4] => 5, [5] => 6);
$idArrayFull = array(1, 2, 3, 4, 5, 6);

function gap($arr)
{
   while (list($k, $v) = each($arr))
      if ($k != ($v-1))
         return $k;
   return -1;
}

print "ok:" . gap($idArrayMissing) . "<br/>\n";
print "full:" . gap($idArrayFull) . "<br/>\n";

The return of the gap function can be 2 values: -1 could indicate that the array has been traversed and there are no free slots or $k+1 which could indicate that the first free slot is on the end of the array.

answered Nov 12, 2010 at 11:50

David Newcomb

11k3 gold badges52 silver badges63 bronze badges

3 Comments

Tim Seguine Over a year ago

Is there a specific reason for using this while idiom instead of foreach($arr as $k => $v)? Also, doesn't this assume that the array is sorted, that the array cursor is zero, and that the values start with 1? And this only gives the first free slot, which is not what the OP asked for exactly.

David Newcomb Over a year ago

The OP did ask for the first free slot! There's no point working out all the values because he's not really interested. You are right with my assumptions. You have missed the fact that my solution won't find gaps at the beginning or end! Besides the example doesn't say that the numbers will be removed or re-inserted, only that the number will be used. list/each is what we used before foreach was added to the language so it's mainly just habit. It should be a lesson to the OP to write questions that specifically produce the results he/she wants without too many assumptions on our part.

Tim Seguine Over a year ago

it says "each missing number"; maybe it said something different when you posted. I wasn't being critical really, I actually like your answer.

Nadeem Khan · Accepted Answer · 2014-10-14 20:27:48Z

0

It can also be done easily by using in_array() function like this:

// lets say $InputArray has all the data
// lets declare a variable which we will search inside the $InputArray array and lets initialize it with either 0 or 1 or with the minimum value found inside $InputArray

$start_counting = 1;
$max_value = count($InputArray);
  if (!(in_array($start_counting, $InputArray)))
   {
      echo "Value: ".$start_counting." is missing!"."<br>" ;
   }
 else{ 
    if($start_counting <= $max_value -1)    
      {$start_counting++;}
     }
    else  if($start_counting > $max_value -1)
     {
      echo "All missing numbers printed!"
     }  
}

edited Oct 14, 2014 at 20:27

answered Oct 14, 2014 at 20:17

Nadeem Khan

3,4341 gold badge34 silver badges44 bronze badges

Collectives™ on Stack Overflow

Find missing numbers in array

6 Answers 6

1 Comment

1 Comment

Comments

Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

1 Comment

Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related