If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
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:
- Looking for ⚒️ tech jobs? Go to our job portal.
- Looking for tech events? Go to tech events 🗓️ Calendar.️
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 |