An algorithm to find the missing number in a progressive sequence [1 .. (N + 1)]

Solution

public int gauss(int[] sequence) {
    long lastValue = sequence.length + 1;
    long total = (lastValue  * (lastValue  + 1)) / 2;
    long sum = 0L;
    for (int i=0; i < sequence.length; i++) {
        sum += sequence[i];
    }
    return (int)(total - sum);
}

NOTES:

  • The long here was used for it be able to calc long sequences as within the range [0..100,000];
  • In Java8 the loop to sum all values can be replaced forArrays.stream(sequence).sum();, however, the performance will be lower
  • The assumption here is that the value is always missed because of it the code sequence.length + 1 is to check if it is not the last one. (E.g [1,2,3,4] the result will be 5)

Mathematical Reference

Screen Shot 2018-01-20 at 8.47.53 PM

NOTE: To know more about it search for Carl Gauss and the Sum of an Arithmetic Series.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s