If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
This is one of basic coding interview question asked in my interviews.
Problem :
You are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. You need to provide optimum solution to find the missing number. Number can not be repeated in the arry.
For example:
|
1 2 3 4 5 6 |
int[] arr1={7,5,6,1,4,2}; Missing numner : 3 int[] arr2={5,3,1,2}; Missing numner : 4 |
Solution:
- Find the sum of n number using formula n=n*(n+1)/2
- Find the sum of elements present in given array.
- Substract (sum of n numbers – sum of elements present in the array).
Java program to find missing number in an 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; } } |
When you run above program, you will get below output:
|
1 2 3 4 |
Missing number from array arr1: 3 Missing number from array arr2: 4 |
