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;
}
}