Find missed number [ Algorithms ]

Hello every one
This is the first algorithm of a series of simple algorithms that we will review here in this blog

If you have list of n-1 integers and these integers are in the range of 1 to n.
EXAMPLE: [ 1, 2, 4, 5, 6, 3, ?, 8 ]    -- n --> 8
No duplicates, one of the integers is missing.
What is the best way to get the missed number ???

There is a simple magic way to do that with a simple formula. If you have a number n you can get the sum from 1 to a given value n ==> n*(n+1)/2 then you can subtract all items of that list and the result is the missed number ;).

For our example:

List => [ 1, 2, 4, 5, 6, 3, ?, 8 ]
n => 8

missed = 8 * ( 8 + 1 ) / 2 - 1 - 2 - 4 - 5 - 6 - 3 - 8 = 7


public static void main(String[] args) {
   System.out.println(getMissedNumber(new int[]{ 1, 2, 4, 5, 6, 3, 8 }, 8));
}

public static int getMissedNumber(int a[], int n) {
   int total;
   total  = (n)*(n+1)/2;
   for ( int i = 0; i < a.length; i++)
      total -= a[i];
   return total;
}

ليست هناك تعليقات:

إرسال تعليق

---- أتشرف بتعليقاتكم ----