Java Program to Find Missing Number in An Array

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

1. Overview

In this article, we will see how to find missing number in Array of 1 to n. This is one of basic coding interview question asked in my interviews.

2. Introduction to Problem Statement

We are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. Our goal is to provide optimum solution to find the missing number. Number can not be repeated in the array.
For example:

If we notice, we have numbers from range of 1 to 5, but 4 is missing in the array.

3. Using Sum Formula

  • Find the sum of n number using formula n=n*(n+1)/2.
  • Find the sum of elements present in given array.
  • Subtract (sum of n numbers – sum of elements present in the array).
When you run above program, you will get below output:

4. Using XOR

Another solution is to use XOR operator.
Here are steps:

  • Declare two variables a=arr[0] and b=1.
  • XOR all elements in the array with a and set it back to a.
  • XOR all elements in the array with b and set it back b.
  • Now XOR a and b and that should give us missing number.

Here is java program:

5. Complexity of Algorithm

Time Complexity: O(N)
Space Complexity: O(1)

6. Conclusion

In this article, we covered two solutions to find missing number in the array. First solution is most simplest one to find missing number in the array while second solution uses xor operator and uses two loops to solve this problem.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *