Write a java program to find missing number in array. Given an array of n-1 integers and these integers are in the range of 1 to n. One of the integer is missing from an array. We have to write an efficient java code to find missing number from an array. An array does not contains any duplicates.
For example –
i) arr = { 1, 2, 3, 4, 6, 7} , Missing number : 5
ii) arr = {4, 5, 1, 2, 6}, Missing number : 3
Algorithm to Find Missing Number in Array
i) First step is to calculate the sum of n natural numbers using formula
totalSum = n*(n+1)/2
ii) In next step, Add the numbers of an array and subtract it from the sum of numbers, we will get the missing number of an array.
We have discussed the algorithm to find missing number in array, Let’s write a java code to implement this solution.
Java Program to Find Missing Number in Array
Java Program to Find Missing Number in Array
The time complexity of this approach is O(n).
Sorting algorithms and their time complexities
|
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 |
public class MissingNumber { public static void main(String[] args) { int[] arr = {3, 4, 5, 1, 6, 7, 8, 9, 10}; /* One number is missing, so n is array length plus 1 */ int n = arr.length + 1; //Calculating sum int sum = (n * (n+1))/2; /* Traversing an array and subtracting each element with the sum */ for(int i = 0; i < arr.length; i++) { sum = sum - arr[i]; } System.out.println( " Missing number is " + sum); } } |
