Bing Lin - 1 year ago 83

PHP Question

Suppose 100 people line up in a circle. Counting from person 1 to person 14, remove person from the circle. Following the count order, counting again and remove the 14th person. Repeat. Who is the last person standing?

I've tried everything to solve this and it seems to not be working with dead loops.

`<?php`

//init array

$array = array();

for ($i = 0; $i < 100; $i++) { $array[] = $i; }

//start from 0

$pos = 0;

while (count_not_null($array) > 1) {

//reset count

$count = 0;

while (true) {

//ignore NULL for count, that position is already removed

if ($array[$pos] !== NULL) {

$count++;

if($count == 14) { break; }

}

$pos++;

//go back to beginning, we cant go over 0-99, for 100 elements

if ($pos > 99) { $pos = 0; }

}

echo "set index {$pos} to NULL!" ."<br>";

$array[$pos] = NULL;

if (count_not_null($array) === 1) { break; }

}

echo "<pre>";

print_r($array);

echo "</pre>";

//counting not null elements

function count_not_null($array) {

$count = 0;

for ($i = 0; $i < count($array); $i++) {

if ($array[$i] !== NULL) { $count++; }

}

return $count;

}

?>

Answer

For solving this with as little code as possible and quickest you could do like this:

```
function josephus($n,$k){
if($n ==1)
return 1;
else
return (josephus($n-1,$k)+$k-1) % $n+1;
}
echo josephus(100,14);
```

Here we are using an recursive statement instead, as what you are trying to solve can be defined by this mathematical statement `f(n,k) = (f(n-1,k) + k) % n`

For reading more about this mathematical formula you can see it here on the wiki page.

Source (Stackoverflow)