Java Interview Questions - Find Missing Number in an Array

	package com.javastructures;

public class FindMissingNumberUsingSummation {

	public static void main(String args[]) {
		// the array whose element is missing
		int a[] = { 1, 2, 4, 5, 6 };

		int missingNumber = findMissingNo(a);
		System.out.println(missingNumber);
	}

	// find missing number
	static int findMissingNo(int a[]) {
		int originalSum, arraySum = 0, missingNumber;

		// since the array is missing an element its original size is + 1
		int n = a.length + 1;
		// Find sum of original array along with the missing number
		originalSum = (n) * (n + 1) / 2;

		// Find sum of the existing array without the missing number
		for (int i = 0; i < a.length; i++) {
			arraySum = arraySum + a[i];
		}

		missingNumber = originalSum - arraySum;
		return missingNumber;
	}

}
	
	

	package com.javastructures;

public class FindMissingNumberUsingXOR {

	public static void main(String args[]) {
		// the array whose element is missing
		int a[] = { 1, 2, 4, 5, 6 };

		int missingNumber = findMissingNo(a);
		System.out.println(missingNumber);
	}

	// find missing number
	static int findMissingNo(int a[]) {
		int missingNumber, x1 = 1, x2 = a[0];

		// since the array is missing an element its original size is + 1
		int n = a.length + 1;

		// Find XOR of all elements of original array along with the missing
		// element
		for (int i = 2; i <= n; i++) {
			x1 = x1 ^ i;
		}

		// Find XOR of all elements of existing array without the missing
		// element
		for (int i = 1; i < a.length; i++) {
			x2 = x2 ^ a[i];
		}

		// XOR both the above results
		missingNumber = x1 ^ x2;
		
		return missingNumber;
	}

}