Is it possible to exclude a for loop from this piece of PHP code?

Question

I have a number of integers that may or may not be present. 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.

Here is how I solved it using the 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 would like to completely eliminate the loop, since the range can be massive. Any suggestions?

Answer 1

EDIT: NOTE
This question is about performance. Functions like array_diff and array_filter are not magically fast. They can add a huge time penalty. Replacing the loop in the code with an array_diff call array_diff not magically speed things up, but will probably make things slower . You need to understand how these functions work if you intend to use them to speed up your code.

This answer uses the assumption that no elements are duplicated or have invalid elements to allow us to use the position of the element to display the expected value.

This answer is theoretically the fastest solution if you start with a sorted list . The solution posted by Jack is theoretically the fastest if sorting is required.

In the series [0,1,2,3,4, ...] the nth element has the value n if there are no elements left in front of it. Therefore, we can check at any time to see if our missing item is before or after the item in question.

So you start by cutting the list in half and checking if the item is at position x = x

 [ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ] ^ 

Yup, list[4] == 4 . So go halfway from the current point to the end of the list.

 [ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ] ^ 

Uh-oh, list[6] == 7 . So, somewhere between our last control point and the current one element was missing. Divide the difference in half and check this element:

 [ 0 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 ] ^ 

In this case, list[5] == 5

So, we are well there. Thus, we take half the distance between our current check and the last, which was abnormal. And oh .. it looks like cell n+1 is the one we already checked. We know that list[6]==7 and list[5]==5 , so element number 6 is missing.

Since each step divides the number of elements that need to be considered in half, you know that your worst performance will check no more than log _{2 of the} total size of the list. That is, this solution is O (log (n)) .

If all of this looks familiar, it is because you learned about it in your second year of college in the Computer Science class. This is a minor variation of the binary search algorithm - one of the most widely used index schemes in the industry. Indeed, this question seems to be a completely contrived application for this search technology.

You can, of course, repeat the operation to find additional missing elements, but since you have already checked the values ​​in the key elements in the list, you can avoid re-checking most of the list and go directly to the interesting ones on the left for testing.

Also note that this decision makes a sorted list. If the list is not sorted, then obviously you are sorting it first. In addition, binary search has some notable properties common with quicksort. It is possible that you can combine the sorting process with the process of finding the missing item and perform both operations in one operation, saving some time.

Finally, to summarize the list, this is just a silly mathematical trick abandoned for good measure. The sum of the list of numbers from 1 to N is simply N*(N+1)/2 . And if you have already determined that any elements are missing, then simply subtract the missing ones.

Answer 2

Algo Solution

There is a way to check if there is a missing number using an algorithm. He explained here . Basically, if we need to add numbers from 1 to 100. We do not need to calculate by summing them, we just need to do the following: (100 * (100 + 1)) / 2 . So how does this solve the problem?

We are going to get the first element of the array and the last. We calculate the sum with this algorithm. Then we use array_sum() to calculate the actual amount. If the results match, then the missing number is missing. Then we could “step back” from the missing number by subtracting the actual amount from the estimated amount. This, of course, only works if there is only one number, and it will fail if there are several missing ones. So put this in code:

  $range = range(0,7); // Creating an array echo check($range) . "\r\n"; // 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 numbers are missing, just use array_map() or something similar to the inner loop.

---

Regression solution

Take it to the next level and use regex! I know this is nonsense and should not be used in the real world. The goal is to show the true power of the regular expression :)

So, first we make a line from 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 look something like this: I,II,III,IIII,IIIII,IIIIII,IIIIIII .

I got the following regular expression: ^(?=(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 matched in group 1 | # or ,\2I # match a comma, with what matched in group 2 (recursive !) and an I | # or \2I # match what matched in group 2 and an I )+ # repeat one or more times $ # match end of line 

Let's see what actually happens ....

 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 the end of string If the number of I don't correspond, then the regex will fail. 

See how it works and doesn't work . And put it in your 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 an account to return a number that is missing, we will remove the end $ character so that our regular expression doesn’t work, and we use group 2 to return the missing 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

Answer 3

Technically, you cannot do without a loop (unless you want to know if there is a missing number). However, you can do this without first sorting the array.

The following algorithm uses O (n) time with O (n) space:

 $range = [0, 1, 2, 3, 4, 6, 7]; $N = count($range); $temp = str_repeat('0', $N); // assume all values are out of place foreach ($range as $value) { if ($value < $N) { $temp[$value] = 1; // value is in the right place } } // count number of leading ones echo strspn($temp, '1'), PHP_EOL; 

It builds an ordered identity mapping from N records, placing each value in its position as "1"; at the end, all entries must be “1”, and the first entry “0” is the smallest value that is missing.

Btw, I use a temporary string instead of an array to reduce physical memory requirements.

Answer 4

I honestly don't understand why you don't want to use a loop. There is nothing wrong with the loops. They are fast, and you simply cannot do without them. However, in your case there is a way to avoid having to write your own loops using the basic PHP functions. However, they loop through the array, but you just can't avoid it.
Anyway, I collect what you need can be easily written in 3 lines:

 function highestPlus(array $in) { $compare = range(min($in), max($in)); $diff = array_diff($compare, $in); return empty($diff) ? max($in) +1 : $diff[0]; } 

Tested with

 echo highestPlus(range(0,11));//echoes 12 $arr = array(9,3,4,1,2,5); echo highestPlus($arr);//echoes 6 

And now, to shamelessly steal the Pé de Leão answer (but to “increase” it to do exactly what you want):

 function highestPlus(array $range) {//an unreadable one-liner... horrid, so don't, but know that you can... return min(array_diff(range(0, max($range)+1), $range)) ?: max($range) +1; } 

How it works:

 $compare = range(min($in), max($in));//range(lowest value in array, highest value in array) $diff = array_diff($compare, $in);//get all values present in $compare, that aren't in $in return empty($diff) ? max($in) +1 : $diff[0]; //------------------------------------------------- // read as: if (empty($diff)) {//every number in min-max range was found in $in, return highest value +1 return max($in) + 1; } //there were numbers in min-max range, not present in $in, return first missing number: return $diff[0]; 

That it is true.
Of course, if the supplied array can contain null or falsy , or even strings, and duplicate values, it may be useful to "clear" the input a bit:

 function highestPlus(array $in) { $clean = array_filter( $in, 'is_numeric'//or even is_int ); $compare = range(min($clean), max($clean)); $diff = array_diff($compare, $clean);//duplicates aren't an issue here return empty($diff) ? max($clean) + 1; $diff[0]; } 

Useful links:

• array_diff page
• max and min functions
• Alright Ol ' range , of course ...
• array_filter function
• array_map function array_map be worth a look
• Just like array_sum can be

Answer 5

 $range = array(0,1,2,3,4,6,7); // sort just in case the range is not in order asort($range); $range = array_values($range); $indexes = array_keys($range); $diff = array_diff($indexes,$range); echo $diff[0]; // >> will print: 5 // if $diff is an empty array - you can print // the "maximum value of the range plus one": $range[count($range)-1]+1 

Answer 6

 echo min(array_diff(range(0, max($range)+1), $range)); 

Answer 7

Plain

 $array1 = array(0,1,2,3,4,5,6,7);// array with actual number series $array2 = array(0,1,2,4,6,7); // array with your custom number series $missing = array_diff($array1,$array2); sort($missing); echo $missing[0]; 

Answer 8

 $range = array(0,1,2,3,4,6,7); $max=max($range); $expected_total=($max*($max+1))/2; // sum if no number was missing. $actual_total=array_sum($range); // sum of the input array. if($expected_total==$actual_total){ echo $max+1; // no difference so no missing number, then echo 1+ missing number. }else{ echo $expected_total-$actual_total; // the difference will be the missing number. } 

Answer 9

you can use array_diff() like this

 <?php $range = array("0","1","2","3","4","6","7","9"); asort($range); $len=count($range); if($range[$len-1]==$len-1){ $r=$range[$len-1]; } else{ $ref= range(0,$len-1); $result = array_diff($ref,$range); $r=implode($result); } echo $r; ?> 

Answer 10

 function missing( $v ) { static $p = -1; $d = $v - $p - 1; $p = $v; return $d?1:0; } $result = array_search( 1, array_map( "missing", $ARRAY_TO_TEST ) );