Find a missing number in an array of distinct integers in java (example)

• Given an array containing n-1 distinct positive numbers range from 1 to n.
  • e.g suppose n = 5, array will contain 4 unique (or no duplicate) numbers.
    • some of the possible array values are
    • int elements[] = { 1, 3, 2, 5 }
      • Missing number is 4
    • int elements1[] = { 1, 2, 4, 5 }
      • Missing number is 3
    • int elements2[] = { 4, 3, 2, 1 }
      • Missing number is 5
• We would like to find out the missing number in an array.
• We will discuss couple of methods to find out the missing number

Method 1: find a missing number in an integer array using Sum (java)

• Calculate the sum of n numbers ( 1 to n).
  • Sum = n * (n + 1) /2, say sumOfNumbers
• Calculate the sum of all elements of input array, say arraySum
• MissingNumber = sumOfNumbers – arraySum

Program: find a missing number using sum formula in java

private static int missingNumberUsingSum(int[] elements) {

	int arraySum = 0;
	// Sum of array
	for (int element : elements) {
		arraySum += element;
	}

	// sum of number from 1 to n
	int n = elements.length + 1; // as one number is missing
	int sumOfNumbers = (n * (n + 1)) / 2;
	return sumOfNumbers - arraySum;
}

Method 2: find a missing number in an integer array using XOR in java

• We will use the properties of XOR gate.
• Truth table of “Exclusive-OR” or XOR gate is :

• Let us apply XOR gate on elements[] = { 1, 3, 2, 5 }
• Calculate XOR of n numbers i.e. 1 to 5 and elements of array
• Missing Number =  (1 ^ 2 ^ 3 ^ 4 ^  5) ^ (1 ^ 3 ^ 2 ^ 5)
• We know XOR (P,P) = 0, let us rearrange same numbers
  • i.e.  (1 ^ 1) ^ ( 2 ^ 2) ^ (3 ^ 3) ^ (4)  ^ (5 ^ 5)
• MissingNumber will be 4.

Program: find a missing number in an integer array using XOR in java

private static int missingNumberUsingXOR(int[] elements) {

	int n = elements.length + 1;
	int missingNumber = elements[0];
	for (int index = 1; index <= n; index++) {
		if (index < elements.length) {
			missingNumber ^= elements[index];
		}
		missingNumber ^= index;
	}
	return missingNumber;
}

Complete program: find a missing number in an integer array (Sum & XOR)

package org.learn.arrays;

import java.util.Arrays;

public class MissingNumber {
	public static void main(String[] args) {

		int elements[] = { 1, 6, 3, 2, 7, 5 };

		String array = Arrays.toString(elements);
		int missingNumber = missingNumberUsingSum(elements);
		System.out.printf("1. Missing number in %s using sum is: %d", array, missingNumber);

		missingNumber = missingNumberUsingXOR(elements);
		System.out.printf("\n2. Missing number in %s using XOR is: %d", array, missingNumber);

		int elements1[] = { 1, 2, 4, 5, 6, 7 };
		array = Arrays.toString(elements1);

		missingNumber = missingNumberUsingSum(elements1);
		System.out.printf("\n3. Missing number in %s using sum is: %d", array, missingNumber);

		missingNumber = missingNumberUsingXOR(elements1);
		System.out.printf("\n4. Missing number in %s using XOR is: %d", array, missingNumber);

		int elements2[] = { 7, 6, 4, 3, 2, 1 };
		array = Arrays.toString(elements2);

		missingNumber = missingNumberUsingSum(elements2);
		System.out.printf("\n5. Missing number in %s using sum is: %d", array, missingNumber);

		missingNumber = missingNumberUsingXOR(elements2);
		System.out.printf("\n6. Missing number in %s using XOR is: %d", array, missingNumber);
	}

	private static int missingNumberUsingXOR(int[] elements) {

		int n = elements.length + 1;
		int missingNumber = elements[0];
		for (int index = 1; index <= n; index++) {
			if (index < elements.length) {
				missingNumber ^= elements[index];
			}
			missingNumber ^= index;
		}
		return missingNumber;
	}

	private static int missingNumberUsingSum(int[] elements) {

		int arraySum = 0;
		// Sum of array
		for (int element : elements) {
			arraySum += element;
		}

		// sum of number from 1 to n
		int n = elements.length + 1; // as one number is missing
		int sumOfNumbers = (n * (n + 1)) / 2;
		return sumOfNumbers - arraySum;
	}
}

Output: find missing number in an array of distinct integers

1. Missing number in [1, 6, 3, 2, 7, 5] using sum is: 4
2. Missing number in [1, 6, 3, 2, 7, 5] using XOR is: 4
3. Missing number in [1, 2, 4, 5, 6, 7] using sum is: 3
4. Missing number in [1, 2, 4, 5, 6, 7] using XOR is: 3
5. Missing number in [7, 6, 4, 3, 2, 1] using sum is: 5
6. Missing number in [7, 6, 4, 3, 2, 1] using XOR is: 5