Find the missing number in the given array of numbers using PHP

Question

Am new to php i have faced an interview some days ago, and the interviewer asked a question like the following one.

The given array has 99 numbers, which contains the digits from 1 to 100 with one digit missing. Describe two different algorithms that finds you the missing number. The algorithm should optimize for low storage and fast processing. Output should show the execution time of each algorithm.

And i have searched google about it, and come to know its a common puzzle used to ask in interviews. I found out the answer like this way.

int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 0) {
         idx = i; 
    } else {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

But the code is not in php,

Can u please help me to find out the php code and algorithm name. So i can improve my answer in the next interviews.

Did you try converting that Java code into PHP? It should be fairly straight forward, when it says arr.length use count($arr), the rest should be pretty much the same. — Alejandro Urbano Alvarez
– Alejandro Urbano Alvarez, Commented Mar 31, 2014 at 11:17

Rikesh · Accepted Answer · 2014-03-31 11:18:26Z

9

In PHP you can easily use some array functions and achieve that. Best way is,

$missing = array_diff(range(1,100),$array);

DEMO.

answered Mar 31, 2014 at 11:18

Rikesh

26.5k14 gold badges82 silver badges90 bronze badges

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

4 Comments

user3480508 Over a year ago

Thank you so much for this quick reply. Did u know any proper algorithm is there to calculate this one?

Rikesh Over a year ago

Can you define what you mean by proper algorithm ?

Abhik Chakraborty Over a year ago

@user3480508 if you try to find an element which is missing within the array this is the shortest way to do it. But if you are looking for time complexity its same as linear/sequential search with O(n) as the time complexity. If you know the element needed to be searched u can apply other good algo like binary search / interpolation search etc which are far better in terms of complexity .

Anthony Over a year ago

array_diff is the best approach because it doesn't presume that the two arrays being compared will be in an ordered, consecutive set. Most data won't be missing one member of the larger set, nor will the larger set likely be one that can be created through range(). The other approaches are clever but are very confined to those unlikely parameters.

Jesper Blaase · Accepted Answer · 2014-03-31 11:22:36Z

1

Another way to do it is by using the array_sum function and the knowledge that all numbers from 1 to 100 added together equals 5050.

$missing = 5050-array_sum($array);

answered Mar 31, 2014 at 11:22

Jesper Blaase

2,41018 silver badges13 bronze badges

1 Comment

Anthony Over a year ago

or just use range to get 5050 : $missing = array_sum(range(1,100)) - array_sum($array);

Keir Lavelle · Accepted Answer · 2014-03-31 13:06:45Z

0

Converted to PHP, it is nearly the same. (Not tested)

Of course, there are better ways, like the one Rikesh posted, but this is the exact one you asked for:

$sum = 0
$idx = -1
for($i = 0; $i < count($arr); $i++){
   if($arr[$i] == 0){
      $idx = $i;
   }else{
      $sum += $arr[$i];
   }
}

$total = (count($arr) + 1) * (count($arr) / 2);

echo "Missing: " . ($total - $sum) . " at index " . $idx;

edited Mar 31, 2014 at 13:06

Keir Lavelle

5232 silver badges18 bronze badges

answered Mar 31, 2014 at 11:23

UeliDeSchwert

1,15610 silver badges23 bronze badges

1 Comment

UeliDeSchwert Over a year ago

Thanks for the correction, Keir. I must have missed this one.

Garima · Accepted Answer · 2015-05-28 06:55:18Z

0

$arr=range(1,99);
$j=1;
for($i=0;$i<100;$i++){
if(!in_array($j,$arr)){
    echo $j.'is missing';
}
$j++;
}

answered May 28, 2015 at 6:55

Garima

691 gold badge2 silver badges10 bronze badges

Collectives™ on Stack Overflow

Find the missing number in the given array of numbers using PHP

4 Answers 4

4 Comments

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related