Table of Contents
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:
|
1 2 3 4 5 6 |
int[] arr1={7,5,6,1,4,2}; Missing number : 3 int[] arr2={5,3,1,2}; Missing number : 4 |
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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package org.arpit.java2blog; public class MissingNumberMain { public static void main(String[] args) { int[] arr1={7,5,6,1,4,2}; System.out.println("Missing number from array arr1: "+missingNumber(arr1)); int[] arr2={5,3,1,2}; System.out.println("Missing number from array arr2: "+missingNumber(arr2)); } public static int missingNumber(int[] arr) { int n=arr.length+1; int sum=n*(n+1)/2; int restSum=0; for (int i = 0; i < arr.length; i++) { restSum+=arr[i]; } int missingNumber=sum-restSum; return missingNumber; } } |
|
1 2 3 4 |
Missing number from array arr1: 3 Missing number from array arr2: 4 |
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
aand set it back toa. - XOR all elements in the array with
band set it backb. - Now XOR a and b and that should give us missing number.
Here is java program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class MissingNumberMain { // Function to find missing number static int getMissingNumberXOR(int arr[], int n) { int a = arr[0]; int b = 1; // Find xor of all the elements in array for (int i = 1; i < n; i++) a = a ^ arr[i]; // Find xor of all the elements from 1 to n+1 for (int i = 2; i <= n + 1; i++) b = b ^ i; int result = a ^ b; return result; } // Main method public static void main(String args[]) { int arr[] = { 5, 3, 1, 2 }; int N = arr.length; // Calling function int missingNumber = getMissingNumberXOR(arr, N); System.out.println("Missing number from array: "+missingNumber); } } |
|
1 2 3 |
Missing number from array: 4 |
