Example:

1
2
3
4
5
+-----------------+----------------------------------------+
| Input | 2, 4, 2, 5, 8, 7, 7, 6, 13, 11, 11, 12 |
+-----------------+----------------------------------------+
| Expected result | 1, 2, 1, 3, 6, 5, 5, 4, 9, 7, 7, 8 |
+-----------------+----------------------------------------+

The input contains missing numbers which are 1, 3, 9, 10. Now the mission is to remove the gap in missing numbers.

Input - result mapping

See the mapping above:

  • infront of 2 there is ONE missing number
  • infront of 4, 5, 6, 7, 8 there are TWO missing number
  • infront of 11, 12, 13 there are FOUR missing number

Can see the pattern?

Now, lets implement it in PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
$input = [2,4,2,5,8,7,7,6,13,11,11,12];
$max_input = max($input);
// find the missing value in ascending order & avoid duplication
$missing_values = [];
for ($i = 1; $i <= $max_input; $i++) {
// skip if current value is not missing OR is already inside the $missing_values container
if (in_array($i, $input) || in_array($i, $missing_values)) continue;
$missing_values[] = $i;
}
$results = [];
foreach ($input as $i) { // goes through all input values
$diff = 0; // this is the `-1`, `-2`, `-4` (green color) on the mapping there
foreach ($missing_values as $mv) {
if ($i < $mv) break;
$diff++; // count the number of missing values infront of current value
}
// finally minus the difference will get the desired result
$results[] = $i - $diff;
}

The output $results will be

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Array
(
[0] => 1
[1] => 2
[2] => 1
[3] => 3
[4] => 6
[5] => 5
[6] => 5
[7] => 4
[8] => 9
[9] => 7
[10] => 7
[11] => 8
)

Done :)