CareerCup

If the sequence is 1, 2, 3, ... , n (order is not required) and only one number is missed, we can just sum all numbers and missed number is equal (n*(n-1)/2 - sum)

Modified binary search is definitely the way to go. If numbers are in sequence, then the difference between two array values should equal the difference of their indices. If not, then the missing number is somewhere in that range.

public static int findMissingNumber(int[] a) {
    // Validate... Assume -1 is fine to return for not found.
    if (a == null || a.length == 0) {
      System.out.println("Invalid sequence: length.");
      return -1;
    }
    int low = 0;
    int mid;
    int high = a.length-1;
    while (low < high) {  
      mid = low + (high - low) / 2;
      if (a[mid] - a[low] == mid - low) {
        // Missing number is in upper half
        if (mid + 1 < a.length && a[mid + 1] != a[mid] + 1)  {
          return a[mid] + 1;
        } else {
          low = mid + 1;
        }
      } else {
        // Missing number is in lower half
        if (mid - 1 >= 0 && a[mid] - 1 != a[mid - 1]) {
          return a[mid] - 1;
        } else {
          high = mid -1;
        }
      }
    }
    System.out.println("Invalid sequence: not found.");
    return -1;
  }

Best case: O(1) Average case: O(log n) Worst case: O(log n)

what is the time complexity? How will you sum all the numbers from an array using loop?,if yes then time complexity will be O(n). Is there any better solution?

@Ragesh

how do you propose to find the sum of all the numbers present in the array without traversing the array at least once? for finding the sum O(n) is  the best you can do. 

Since you haven't mentioned what the sequence is i am assuming it to be an Arithmetic progression .

 Lets assume the sequence is of the form of an arithmetic progression so according to the formula 
a(n) = first_term +(n-1)common_difference 
while iterating over the array check that for every iteration the next number fits the above equation 
lets say at kth element  the above   equation is not satisfied break your loop & print a(k).
complexity O(k+k) ~ O(k) 
worst case complexity O(n)

If you know the expected difference between the values you could just loop through and when you spot a difference between index i and i +1 you could just abort when you find the missing value. On average you need to loop through
n/2 but worst case is n, so this will be O(n)

If the numbers are Sorted we can use a modification of the Binary Search to look for the missing number this will give us a O(logN) time complexity, the idea is to compare the value in the array with the index to determinate witch part of the array is going to be discarded.

public static int FindMissingInSequence(int[] a)
{
	int missing = 0;
	int start = 0; 
	int end = a.Length - 1;
		
	while (start < end)
	{
		int midle = (start + end) / 2;
		
		if (midle + 1 == a[midle])
			start = midle + 1;
		else
			end = midle - 1;
	}
	
	if (start > end)
		return -1;
	
	return (start + 1 == a[start]) ? a[start] + 1 : a[start] - 1;
}

In the case that the sequence doesn't start from 1 a small modification is required.

For the other discussion, to sum the values, an alternative is to use XOR operation, this way is preferred because in the case of a big array with big numbers an overflow can be reached. In this algorithm we have O(N) time complexity so the binary approach is preferred.

public static int FindMissingInSequence(int[] a)
{
	int missing = 0;
	for (int i=0; i < a.Length; i++)
	{
		missing = missing ^ a[i];
	}
	
	
	for (int i=1; i <= a.Length + 1; i++)
	{
		missing = missing ^ i;
	}
	
	return missing;
}

If the numbers are sorted:

public class MissingNumber {
	
		public static void main(String[] args) {
			// TODO Auto-generated method stub
			int arr[] = {22, 23 ,24 , 25 , 26 , 27 , 28 , 29 ,  31 , 32 , 33 , 34};
			System.out.println(binarySearch ( arr , 0 , arr.length - 1 , arr.length - 1));
		}
	
		private static int binarySearch(int[] arr , int start , int end , int lastIndex) {
			// TODO Auto-generated method stub
			if ( start > end)
				return -1;
			
			int mid = ( start + end ) / 2;
			if  ( mid-1 >=0 && arr[mid]-1 != arr[mid-1] )	{
				return arr[mid] - 1;
			}
			else if ( mid+1 <= lastIndex && arr[mid+1] != arr[mid] + 1)	{
				return arr[mid]+1;
			}
			else	{
				if ( arr[mid] - arr[0] == mid - 0)	{
					return binarySearch(arr ,  mid+1, end, lastIndex);
				}
				else	{
					return binarySearch ( arr , start , mid - 1 , lastIndex);
				}
			}
		}
	
	}

The sum of numbers from 1 to N is: N*(N+1)/2.
We can calculate this sum and compare it with the real sum of array elements.
The difference will be our missing number.

Binary Search.
Any number at index 'r' can be represented as a+r*d (a is starting number, d is diff)
if the number at 'mid' does not match the expectation, then the missed number already happened, so look in left half of the array, else look in right half of array.
Also, to calculate diff, we need to make sure that diff between a[i] and a[i+1] and a[i+1] and a[1+2] is same (as it might be missed number already happened).
Time complexity: O(log(n))