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