Find missing number

Algorithm

An array contains n-1 unique integers in the range [0,n-1]that is there one number from the range that is not in A. Design an O(n) time algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself

Missing number (A,size)//returns the missing element in the array A

1.	Initialize sum_n:=0 and sum_arr:=0;
2.	Repeat steps 3 to 5 for i=0 to size
3.	Set sum_n := sum_n + i;
4.	If i<size then
5.	Set sum_arr := sum_arr + arr[i];
6.	[end of step 2]
7.	Set mis_num := sum_n – sum_arr;
8.	Return mis_num;
9.	[end]

Algorithm Description


Java Code

/*to find the integer missing in the range [0,n-1] from an array 
containing n-1 unique integers*/

import java.io.*;
class find
{
	public static void main(String args[]) throws Exception
	{
		int n,i,sum=0;
		BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
		System.out.println("enter the no. of elements in the array");
		n=Integer.parseInt(br.readLine());
		int arr[]=new int[n];
		System.out.println("enter the integers from 0 to "+n);
		for(i=0;i<n;i++)
		{
			arr[i]= Integer.parseInt(br.readLine());
		}
		for(i=0;i<n;i++)
			sum=sum+arr[i];
		sum=n*(n+1)/2 -sum;
		System.out.println("the integer not present is :"+sum);
	}
}