arrays - Can the for loop be eliminated from this piece of PHP code?

Question

I have a range of whole numbers that might or might not have some numbers missing. Is it possible to find the smallest missing number without using a loop structure? If there are no missing numbers, the function should return the maximum value of the range plus one.

This is how I solved it using a for loop:

$range = [0,1,2,3,4,6,7];

// sort just in case the range is not in order
asort($range);
$range = array_values($range);

$first = true;
for ($x = 0; $x < count($range); $x++)
{
    // don't check the first element
    if ( ! $first )
    {
        if ( $range[$x - 1] + 1 !== $range[$x])
        {
            echo $range[$x - 1] + 1;
            break;
        }
    }

    // if we're on the last element, there are no missing numbers
    if ($x + 1 === count($range))
    {
        echo $range[$x] + 1;
    }
    $first = false;
}

Ideally, I'd like to avoid looping completely, as the range can be massive. Any suggestions?

Answer 1

Algo solution

There is a way to check if there is a missing number using an algorithm. It's explained here. Basically if we need to add numbers from 1 to 100. We don't need to calculate by summing them we just need to do the following: (100 * (100 + 1)) / 2. So how is this going to solve our issue ?

We're going to get the first element of the array and the last one. We calculate the sum with this algo. We then use array_sum() to calculate the actual sum. If the results are the same, then there is no missing number. We could then "backtrack" the missing number by substracting the actual sum from the calculated one. This of course only works if there is only one number missing and will fail if there are several missing. So let's put this in code:

  $range = range(0,7);  // Creating an array
  echo check($range) . "
"; // check
  unset($range[3]); // unset offset 3
  echo check($range); // check
    
  function check($array){
    if($array[0] == 0){
      unset($array[0]); // get ride of the zero
    }
    sort($array); // sorting
    $first = reset($array); // get the first value
    $last = end($array); // get the last value
    $sum = ($last * ($first + $last)) / 2; // the algo
    $actual_sum = array_sum($array); // the actual sum
    if($sum == $actual_sum){
      return $last + 1; // no missing number
    }else{
      return $sum - $actual_sum; // missing number
    }
  }

Output

8
3

Online demo

If there are several numbers missing, then just use array_map() or something similar to do an internal loop.

---

Regex solution

Let's take this to a new level and use regex ! I know it's nonsense, and it shouldn't be used in real world application. The goal is to show the true power of regex :)

So first let's make a string out of our range in the following format: I,II,III,IIII for range 1,3.

$range = range(0,7);
if($range[0] === 0){ // get ride of 0
  unset($range[0]);
}

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
echo $str;

The output should be something like: I,II,III,IIII,IIIII,IIIIII,IIIIIII.

I've come up with the following regex: ^(?=(I+))(^1|,2I|2I)+$. So what does this mean ?

^                   # match begin of string
(?=                 # positive lookahead, we use this to not "eat" the match
    (I+)            # match I one or more times and put it in group 1
)                   # end of lookahead
(                   # start matching group 2
    ^1             # match begin of string followed by what's matched in group 1
        |           # or
    ,2I            # match a comma, with what's matched in group 2 (recursive !) and an I
        |           # or
    2I             # match what's matched in group 2 and an I
)+                  # repeat one or more times
$                   # match end of line

Let's see what's actually happening ....

I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
(I+) do not eat but match I and put it in group 1

I,II,III,IIII,IIIII,IIIIII,IIIIIII
^
^1 match what was matched in group 1, which means I gets matched

I,II,III,IIII,IIIII,IIIIII,IIIIIII
 ^^^ ,2I match what was matched in group 1 (one I in thise case) and add an I to it

I,II,III,IIII,IIIII,IIIIII,IIIIIII
    ^^^^ 2I match what was matched previously in group 2 (,II in this case) and add an I to it

I,II,III,IIII,IIIII,IIIIII,IIIIIII
        ^^^^^ 2I match what was matched previously in group 2 (,III in this case) and add an I to it

We're moving forward since there is a + sign which means match one or more times,
this is actually a recursive regex.
We put the $ to make sure it's the end of string
If the number of I's don't correspond, then the regex will fail.

See it working and failing. And Let's put it in PHP code:

$range = range(0,7);
if($range[0] === 0){
  unset($range[0]);
}

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
if(preg_match('#^(?=(I*))(^1|,2I|2I)+$#', $str)){
  echo 'works !';
}else{
  echo 'fails !';
}

Now let's take in account to return the number that's missing, we will remove the $ end character to make our regex not fail, and we use group 2 to return the missed number:

$range = range(0,7);
if($range[0] === 0){
  unset($range[0]);
}
unset($range[2]); // remove 2

$str = implode(',', array_map(function($val){return str_repeat('I', $val);}, $range));
preg_match('#^(?=(I*))(^1|,2I|2I)+#', $str, $m); // REGEEEEEX !!!

$n = strlen($m[2]); //get the length ie the number
$sum = array_sum($range); // array sum

if($n == $sum){
  echo $n + 1; // no missing number
}else{
  echo $n - 1; // missing number
}

Online demo