Finding missing number from series

Question

This code will accept user input from the command line.

The first user can enter the limit of series.

e.g: user may enter 5

After that, the user will be prompted for 5 numbers of a series.

e.g:

2 4 8 10 12

Here in this series, 6 is missing, so I am going to find the missing series from common difference series.

I got the correct output from this code. Is it the correct way? Is there any other simple code to do the same?

<?php
    fscanf(STDIN, "%d\n", $count);
    $series = array();
    $common_diff = array();
    $prev_element = null;
    for($i=0;$i<$count;$i++){
        fscanf(STDIN, "%d\n", $series[$i]);
        if($prev_element != null){
            $common_diff[] = $series[$i] - $prev_element;
        }
        $prev_element = $series[$i];
    }
    $c = array_count_values($common_diff);
    asort($c);
    end($c);
    $common_d = key($c);
    $prev_element = $series[0];
    $missed_no = 0;
    for($i=1;$i<$count;$i++){
        $diff = $series[$i] - $prev_element;
        if($diff != $common_d){
            $missed_no = $prev_element + $common_d;
        }
        $prev_element = $series[$i];
    }
    echo $missed_no;
    exit;
?>

example input

5 2 4 8 10 12

is it possible for more than 1 values to be missing? are series of 1 allowed? Are you considering negatives/invalid input? — Elias Van Ootegem
– Elias Van Ootegem, Commented Jan 31, 2014 at 10:27

Paul · Accepted Answer · 2014-01-31 12:40:11Z

Functions

The code can be more readable if it is broken into functions. This also separates the concern of reading in the series and calculating the missing element(s).

function readSeries($fileHandle)
{
    $series = array();
    fscanf($fileHandle, "%d\n", $count);

    for ($i = 0; $i < $count; ++$i)
    {
        fscanf($fileHandle, "%d\n", $series[$i]);
    }

    return $series;
}

function findMissing(Array $series)
{
    sort($series);
    $start = reset($series);
    $finish = end($series);
    $step = ($finish - $start) / count($series);    

    return array_diff(range($start, $finish, $step),
                      $series);
}

$series = readSeries(STDIN);
$missing = findMissing($series);
echo reset($missing);

The use of functions also help to make the code more reusable. The readSeries function can easily be used to read from standard input or another source.

The findMissing function takes advantage of some assumptions that can be made when a series is sorted:

It would be impossible to notice whether the beginning or end elements were missed, so they must both be present.
One the beginning and end values are known then every step along this range must be present.

It then uses the difference of the expected series calculated using the PHP range function.

Elias Van Ootegem · Accepted Answer · 2014-01-31 10:40:34Z

Right, I'd fill in the missing values like so:

//assume
$series = array(2,4,8,10,12);
$count = 5;
//get step-size:
$step = floor((max($series) - min($series))/$count);
//then check/complete series:
$complete = array($series[0]);//first element is valid
for($i=1, $j=count($series);$i<$j;++$i)
{
    while(end($complete) + $step < $series[$i]
    {//while the complete series + step, add missing value
        $complete[] = end($complete) + $step;
    }
    $complete  = $series[$i];
}

Now this is far from perfect, but it's a start

Stack Exchange Network

Finding missing number from series

2 Answers 2

Functions

You must log in to answer this question.

Hot Network Questions

Finding missing number from series

2 Answers 2

Functions

You must log in to answer this question.

Related

Hot Network Questions