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

Leave a Comment / By /
  • 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 :
X Y  Output
0 0  0
0 1 1
1  0  1
1  1 0
  • 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

You may also like:

Prime number generator in java using Sieve of Eratosthenes algorithm

Majority element in integer array (Boyer Moore’s voting algorithm) in java

Find leader elements/numbers in integer array (java/example/iterative algorithm)

Replace every element in integer array by greatest number on its right (java/ example)

Find intersection/common elements of two sorted integer arrays in java (example)

Find union of two sorted integer or number arrays in java (example)

Reverse an integer array in java using iterative & recursive algorithm