Sunday, September 24, 2023

How to Find Missing Number on Integer Array of 1 to 100 - BitSet Example

One of the most frequently asked questions on programming interviews are, write a program to find the missing number in an array in Java, C#, or any other language; depending upon which language you choose. This kind of coding interview questions are not only asked in small start-ups but also on some of the biggest technology companies like Google, Amazon, Facebook, Microsoft, mostly when they visit the campus of reputed universities to hire graduates. The simplest version of this question is to find missing elements in an area of 100 integers, which contains numbers between 1 and 100. 

This can easily be solved by calculating the sum of the series using n(n+1)/2, and this is also one of the quickest and efficient ways, but it cannot be used if the array contains more than one missing number or if the array contains duplicates.

This gives the interviewer some nice follow-up questions to check whether a candidate can apply his knowledge of a slightly different condition or not. So if you get through this, they will ask you to find the missing number in an array of duplicates. 

This might be tricky but you will soon find out that another way to find missing and duplicate numbers in the array is to sort it.

In a sorted array, you can compare whether a number is equal to the expected next number or not. Alternatively, you can also use BitSet in Java to solve this problem.




Java Program to find missing numbers

Java Program to find Missing number in Array
Let's understand the problem statement, we have numbers from 1 to 100 that are put into an integer array, what's the best way to find out which number is missing? If Interviewer especially mentions 1 to 100 then you can apply the above trick about the sum of the series as shown below as well. 


If it has more than one missing element that you can use BitSet class, of course only if your interviewer allows it.

1) Sum of the series: Formula: n (n+1)/2( but only work for one missing number)
2) Use BitSet, if an array has more than one missing element.

I have provided a BitSet solution with another purpose, to introduce with this nice utility class. In many interviews, I have asked about this class to Java developers, but many of them not even aware of this. I think this problem is a nice way to learn how to use BitSet in Java as well.

By the way, if you are going for interview, then apart from this question, its also good to know how to find duplicate numbers in array and program to find second highest number in an integer array. More often than not, those are asked as follow-up question after this.


import java.util.Arrays;
import java.util.BitSet;
 
/**
 * Java program to find missing elements in a Integer array containing 
 * numbers from 1 to 100.
 *
 * @author Javin Paul
 */
public class MissingNumberInArray {
 
    public static void main(String args[]) {

        // one missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
 
        // two missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        // three missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        // four missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
 
        // Only one missing number in array
        int[] iArray = new int[]{1, 2, 3, 5};
        int missing = getMissingNumber(iArray, 5);
        System.out.printf("Missing number in array %s is %d %n"
                           Arrays.toString(iArray), missing);
    }

   /**
    * A general method to find missing values from an integer array in Java.
    * This method will work even if array has more than one missing element.
    */
    private static void printMissingNumber(int[] numbers, int count) {
        int missingCount = count - numbers.length;
        BitSet bitSet = new BitSet(count);
 
        for (int number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
        Arrays.toString(numbers), count);
        int lastMissingIndex = 0;

        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }

   /**
    * Java method to find missing number in array of size n containing
    * numbers from 1 to n only.
    * can be used to find missing elements on integer array of 
    * numbers from 1 to 100 or 1 - 1000
    */
    private static int getMissingNumber(int[] numbers, int totalCount) {
        int expectedSum = totalCount * ((totalCount + 1) / 2);
        int actualSum = 0;
        for (int i : numbers) {
            actualSum += i;
        }
 
        return expectedSum - actualSum;
    }
 
}
 
Output
Missing numbers in integer array [1, 2, 3, 4, 6], with total number 6 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 9, 8], with total number 10 is
5
7
10
Missing numbers in integer array [1, 2, 3, 4, 9, 8], with total number 10 is
5
6
7
10
Missing number in array [1, 2, 3, 5] is 4

You can see that how using the right data structure can solve the problem easily. This is the key takeaway of this program, for the more coding question, you can check these coding interview courses and the classic coding interview book, Cracking the Coding Interviews, a collection of 189 coding questions from programming interviews of tech companies like Google, Amazon, Microsoft, and others.



That's all on this program to find missing element in an array of 100 elements. As I said, it's good to know the trick, which just require you to calculate sum of numbers and then subtract that from actual sum, but you can not use that if array has more than one missing numbers. 

On the other hand, BitSet solution is more general, as you can use it to find more than one missing values on integer array. For more programming questions, you can also check here.

And lastly one question for you? Which one is your favorite Java coding exercise? Palindrome, Armstrong number, reverse an array,  Prime number, Fibonacci, Factorial or this one? 

72 comments :

SARAL SAXENA said...

@Javin..really cool one , lem me add more for developers :)
This was an Amazon interview question ....
Solution for that it was ....
1) Calculate the sum of all numbers stored in the array of size 51.
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.

but anyways I have also come up with the approach that uses XOR..

We can use XOR operation which is safer than summation because in programming languages if the given input is large it may overflow and may give wrong answer.

Before going to the solution A xor A = 0 so if we xor two identical number the value is Zero.

// Assuming that the array contains 99 distinct integers between 1..99 and empty slot value is zero
for(int i=0;i<100;i++)
{
if(ARRAY[i] != 0)
XOR ^= ARRAY[i];
XOR ^= (i + 1);
}
return XOR;

Anonymous said...

@Saral, what is the initial value of XOR here, I am guess it's zero, right?

Anonymous said...

There are many ways to search an element in array :
1) linear search involves comparing each element to expected value, complexity O(n)
2) If array is sorted then you can also use binary search, compexity O(logN)

I would prefer binary search because of it's performance.

Unknown said...

class FindMissingElement
{
void printMissingElement(int[] numbers,int totalelement)
{
int i=0;
boolean missingElement;
while(i<totalelement)
{
missingElement=true; // initialized to true means element is missing.
for(int j=0;j<numbers.length;j++)
{
if(totalelement==numbers[j]) // each array element with totalelement.
{
missingElement=false; // means element is not missing.
}
}
if(missingElement==true)
{
System.out.println(totalelement);
}
--totalelement;
}
}
public static void main(String args[])
{
int elements[]=new int[]{2,4,7,5}; // integer array
FindMissingElement me=new FindMissingElement();
me.printMissingElement(elements,7); // passing array element and total element.
}
}

javin paul said...

hello @Ankit, I guess your forgot to put the output of your program, nice solution though.

Anuj said...

private static void findMissingNumber(int[] number){
for (int i = 0; i < number.length -1; i++) {
int j = i+1;
int difference = number[j] - number[i] ;
if(difference != 1){
int missing_num = number[i] + 1;
for (int k = difference; k > 1 ; k--) {
System.out.println("Missing Number is " + missing_num);
missing_num++;
}
}
}
}

Anonymous said...

hi java i think ur solution will not work ...if array is not sorted......for ex: int [] a={ 1,6,5,3,4}

Anonymous said...

package practice;
import static java.lang.System.*;
public class arr1 {

public static void main(String[] args)
{
int [] a ={1,7,3,5,6,8,10,9};
int l=a.length;
int c=1;

//SORT THE ARRAY
for(int i=0;ia[i+1])
{
int temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}


//CHECK FOR MISSING
for(int i=0;i<l;i++)
{
if(a[i]!=c)
{
out.println(c+" " + "not present");
c=c+2;
}
else
c++;

}
// TODO Auto-generated method stub

}

}

Anonymous said...

Why not just add all the number, and subtract the calculate sum with expected sum, if array doesn't contain any duplicates then result is your missing number. This logic will work in any programming language e.g. Go, Rust, Ruby, Python, C, C++ or even JavaScript, becasue it doesn't use language specifice feature, like JDK class BitSet

Anonymous said...

void printMissingElement(final int[] numbers, int totalelement) {
List asList = new ArrayList<>();
for (int i = 0; i < numbers.length; i++) {
asList.add(numbers[i]);
}

while (totalelement >= 1) {
if (!asList.contains(totalelement)) {
System.out.println("missing element : " + totalelement);
}
totalelement--;

}
}

Unknown said...

Hello Guys,

I have a one more solution for the same problem, which is more efficient way because the code has XOR operation,


public class MissingElementsInArray {

public static void main(String[] args) {

int [] a = {1,3,4,5};
System.out.println("The Value is :"+findMissingNumberInSequentialArray(a));
}

public static int findMissingNumberInSequentialArray(int[] a){
int xorCalulated = 1;
for(int i=2;i<=a.length;i++) // this loop runs (n) times
xorCalulated^=i;

int xorActual=a[0];
for(int i=1;i<(a.length-1);i++) // this loop runs (n-1) times. Since there is one element "missing"
xorActual^=a[i];

return xorActual^xorCalulated;

}

}

thewolf said...

In Java you must force to decimal operation in ((totalCount + 1) / 2) because the result here is 60, the correct operation in Java is

int expectedSum = (int) (totalCount * ((float) (totalCount + 1) / 2));

Unknown said...

check this

public class FindNumber
{

public static float findNumber(int[] number,float count)
{

float expectedsum =count*((count+1)/2);
System.out.println(expectedsum);
float acsum=0;
for (float i:number)
{
acsum+=i;
}

return expectedsum -acsum;

}
public static void main(String[] args) {
System.out.println(findNumber(new int[]{1,2,3,4,6},6));

}

}

it type int then wrong answer so we should take float type

Unknown said...

How is it
class MissingElement
{
public static void main(String []args){
int[] a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20};
int i,j,c;
for(i=1;i<a.length;i++){

if((a[i]-a[i-1])!=1){
c=a[i+1]-1;
System.out.println(" Missing element is : "+c);

}


}
}
}

Unknown said...

Hi Rajesh,

I think c=a[i+1]-1; should be c=a[i-1]+1;
And thank you for the post

Unknown said...

Hi,

I couldnt get you BitSet solution,


Also i have something implemented and working :)


// {2,3,6,7,8} //8
private static void printMissingNumbers(int[] number,int count){
int missingCounts=count - number.length;
int countAllMissings=0;

for(int i=1;i<count;i++){

if(number[i-1-countAllMissings] != i){
System.out.println("missing number " + i);
countAllMissings++;
}

}

}

Anurag said...

Comment by Wolf is correct, Method getMissingNumber(int[] numbers, int totalCount) is not giving correct result for all case. it must be changed as below.

int expectedSum = (int) (totalCount * ((float) (totalCount + 1) / 2));

Read more: http://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html#ixzz4In9UvFTk


10 Simple way anyone can impress a girl said...

Int[] input={121,122,123,124,125,126,127,128,129};
Output should be:{123,124,125,126,127,128,129}
Since 121 and 122 as repeated number. 121 has two 1's and 122 as two 2's so that two number should be removed. Any one suggest me the code.

Anonymous said...

public class MissedElmtInArry {

public static void main(String[] args) {
int i,sum=0, expsum=0,n=5;
int a[]={1,2,4,5};
for(i=0;i<4;i++)
sum=sum+a[i];
System.out.println("Actual Sum: "+sum);
expsum = n*((n+1)/2);
System.out.println("result:"+(expsum-sum));
}
}

Unknown said...

package com.java.interview.program;

import java.util.Scanner;

public class MissingNUmberofArry {

public static void main(String[] args) {
int limit;
Scanner sc=new Scanner(System.in);
System.out.println("enter array list");
limit=sc.nextInt();
int arr[]=new int[limit];
for(int i=0;i<limit;i++)
{
arr[i]=sc.nextInt();
}
System.out.println("array data is");
for(int i=0;i<limit;i++)
{
System.out.println(arr[i]);
}
int total=(limit+1)*(limit+2)/2;
System.out.println(total);
for(int i=0;i<limit ;i++)
{
total -=arr[i];
}

System.out.print("Missing value is"+total);
}

}

Umesh said...

@thewolf, @Anurag

You have correctly pointed out the mistake in following line:
int expectedSum = totalCount * ((totalCount + 1) / 2);

However rather than conversion, simplest solution would be doing multiplication first as below:
int expectedSum = totalCount * (totalCount + 1) / 2;

Just remove the braces :)


Anonymous said...

It can also be done by:

private static void find(int[] arr)
{
int new_arr[] = new int[arr[arr.length-1]];
int l = 0;
//if you don't have array 1st element as 1.
if(arr[0] != 1)
{
for(int x =1;x<arr[0];x++)
{
new_arr[l] = x;
l++;
}
}

for(int i = 0;i<arr.length-1;i++)
{
int j = i+1;
int diff = arr[j] - arr[i];

if(diff != 1)
{
for(int x=1;x<diff;x++)
{
new_arr[l] = arr[i] + 1;
l++;
}
}
}

for(int s=0;s<l;s++)
{
sysout(" "+new_arr[s]);
}
}

Anonymous said...

In case to find missing numbers between 100 to 106 e.g.- 100, 101, 102, 104, 105, 106
- Your code printMissingNumber() won't work.

Suresh said...

public int missingNumber(int [] arr,int count){
int total = count*(count+1)/2;
int sumOfArray = 0;
for(int i = 0;i<arr.length;i++){
sumOfArray += arr[i];
}
return total - sumOfArray;
}

Unknown said...


int[] a=new int[]{1,2,3,4,6,8,10};
int missing=0;
for(int i=0;i<a.length-1;i++)
{
if(a[i+1]-a[i]!=1)
{
missing=a[i]+1;
System.out.println("missing number is"+missing);
}
}

Unknown said...

//2, 4, 1, 6, 3 repetition of numbers not allowed


#include
int main(){
int n = 5;
int arr[5] = {2, 4, 5, 1, 3};

int x = n+1; // 6
int sum = 0;
sum = x*(x+1)/2;

int i = 0;
int sum1 = 0;

for(i = 0; i<n; i++){
sum1 = sum1 + arr[i]; // 0 + 2 + 4 + 1 + 6 + 3
}

printf("missing number = %d", sum - sum1);

return 0;
}
for better understanding please watch this video https://www.youtube.com/watch?v=qniYC1S7VxQ&t=8s

Nipun said...

@Javin If array contains element from 50 to 55 like {50,51,53,55} then this solution of finding missing numbers wont work.
How to implement solution to handle this solution?? [Java]

javin paul said...

Hello Nipun, you can still use the same technique but with different formula e.g. n*(a + l)/2 which gives you sum of n numbers, where a and l is first and last number. Btw, the solution will only work if there is only one missing number, if you have two or more, you need to use a hashset

Rancho said...

Hello Javin, Thanks for sharing knowledge.Recently i was asked to "write a program to find the missing numbers(more than one number) in unsorted array (lower and upper range and size of array was given) without using any Java API and only 1 iteration is allow". Could you please help.

Anonymous said...

public static void main(String[] args) {
int[] arr = new int[] {1,2,3,6,7,10,15};
printMissing(arr);
}

static void printMissing(int[] arr) {
for(int i=1;i<arr.length;i++) {
if(arr[i]-arr[i-1]!=1) {
for(int j=arr[i-1] +1;j<arr[i];j++) {
System.out.println(j);
}
}
}
}

Unknown said...

How about this solution :

public class MissingNumber {
public static void main(String[] args)
{
int[] array = new int[]{25,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,20,16,22,21,24,2,0,0,0};
int z = 0;
int n = array.length;

int[] missingNumber = new int[10];

for(int j = 1;j<=n;j++)
{
for(int i = 0;i<n;i++) {

if (j == array[i]) {
break;
}
else if(j!=array[i] && i == n-1)
{
missingNumber[z] = j;
z++;
}
}

}

System.out.println("Missing numbers:");
for(int y= 0;y<z;y++)
{
System.out.println(missingNumber[y]);
}

}
}

Yash Shrivastav said...

I have seen many commenting this solution, but the problem with above provided solution is that. it does not searches for maximum element.

import java.util.Arrays;
public class FindMissingElement
{
void MissingElement(int[] numbers,int totalelement)
{
Arrays.sort(numbers);
int ind=0;
for(int i=1;i<numbers.length;i++)
{
if(numbers[i]-numbers[i-1]!=1)
{
System.out.println(numbers[i-1]+1);
}
}
/*ind=numbers[numbers.length-1];
if(ind<totalelement)
{
for(int i=ind+1;i<=totalelement;i++)
System.out.println(i);
}*/
}

public static void main(String args[])
{
int array[]=new int[]{1,2,3,4,6,9,8};
FindMissingElement number=new FindMissingElement();
number.MissingElement(array,10);
}
}

J. Ernesto Aneiros said...

Interesting problem but very long solution, see below:

Set s1 = new HashSet<>(Arrays.asList(new Integer[]{1, 2, 3, 4, 9, 8}));
Set s2 = new HashSet<>(IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList()));

s2.removeAll(s1);
System.out.println(s2);

J. Ernesto Aneiros said...

The posting ate some portions of my code:

Set s1 = ... and Set s2 = ...

J. Ernesto Aneiros said...

Set<Integer> s1 = ...
Set<Integer> s2 = ...

javin paul said...

Hello j anerious, nice solution.

J. Ernesto Aneiros said...

To Javin: The Occam razor, my friend.

J. Ernesto Aneiros said...

In fact, this one is simpler and closer to the spirit, I think:

List<Integer> L1 = Arrays.asList(new Integer[]{1, 2, 3, 4, 9, 8});
List<Integer> L2 = IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toCollection(ArrayList::new));

L2.removeAll(L1);
System.out.println(L2);

Collections, collections, collections ...

Anonymous said...

What is the logic behind 'bitSet.set(number - 1)'.

Unknown said...

public class MissingNo {
int c = 1;
public void miss(int a[]) {

for(int i=0;i<a.length;i++) {
if(a[i] == c) {
}
else {
System.out.println(c);
break;
}

c++;
}

}

public static void main(String[] args) {
MissingNo b = new MissingNo();
int a[] = {1,2,3,4,5,6,7,8,9,10,11,13};
b.miss(a);
}

J. Ernesto Aneiros said...

@SAURABH MAHESHWARI

Your solution implies a sorted array from low to high, even a sorted array in decrease order will fail and it will print only one missing value. The if could be simplify using not and the way you are declaring the array although is accepted by the compiler is not the clearer.

Sravanth kumar said...

What u said is absolutely correct logic......

Unknown said...

Hi Tried your code. having some mistake in your code.
// Only one missing number in array
int[] iArray = new int[]{1, 2, 3, 4, 5, 6, 7, 9, 10};
int missing = getMissingNumber(iArray, 10);
System.out.printf("Missing number in array %s is %d %n",

Arrays.toString(iArray), missing);


private static int getMissingNumber(int[] numbers, int totalCount) {
int expectedSum = totalCount * ((totalCount + 1) / 2);


int actualSum = 0;
for (int i : numbers) {
actualSum += i;
}
System.out.println(expectedSum+" "+actualSum);
return expectedSum - actualSum;
}

OUTPUT : Missing number in array [1, 2, 3, 4, 5, 6, 7, 9, 10] is 3

it's wrong. Expected output is 8.

javin paul said...

Hello @Vinodh, thanks for pointing it out, will check.

Ahsan Khan said...

I think this will only work for binary search!

Unknown said...

int a[] = {1,2,3,5,7,9,12,12,20};
int missing=0;
for(int i=0;i<a.length-1;i++)
{
if(a[i+1]-a[i]!=1)
{
missing=a[i]+1;
System.out.println("missing number is"+missing);

if(missing+1 != a[i+1]) {
for (int k = missing+1; k<a[i+1]; k++) {
System.out.println("missing number is"+k);
}
}
}
}

Sarvesh Patel said...

import java.util.ArrayList;

public class HowToFindTheMissingNumberInIntegerArray {

public static void main(String[] args) {
int[] BaseArray = new int[100];
for (int i = 0; i < 100;) {
BaseArray[i] = i + 1;
System.out.print(BaseArray[i]+" ");
i = i + 2;
}
System.out.println("\n missing element in above printed list between 1 to 100");
missingNumberInArray(BaseArray, 100);
}

private static void missingNumberInArray(int[] baseArray, int i) {
for (int j = 0; j < i; j++) {
int a = j + 1;
if (baseArray[j] != a) {
System.out.print(a+" ");
}
}
}
}

Unknown said...

how to write in c language

thuhpatrick said...

DON'T USE INTEGERS FOR DIVIDING!
Yes, you need to calculate the series by n((n+1)/2). If n is even, then n+1 will be odd. If you divide an odd number by 2, you will get the even division without the remainder. The solution would be to either declare expectedSum and actualSum to doubles and then cast the difference to an integer before returning the value.

Unknown said...







What is role of Bitset() constructor at every point plzz explain me.
Thank you...


private static void printMissingNumber(int[] numbers, int count) {
int missingCount = count - numbers.length;
BitSet bitSet = new BitSet(count);

for (int number : numbers) {
bitSet.set(number - 1);
}

System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
Arrays.toString(numbers), count);
int lastMissingIndex = 0;

for (int i = 0; i < missingCount; i++) {
lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
System.out.println(++lastMissingIndex);
}

}

Unknown said...

for (int number : numbers) {
bitSet.set(number - 1);
}
and
for (int i = 0; i < missingCount; i++) {
lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
System.out.println(++lastMissingIndex);
}
how these two functons word inside each loop?
Actually how BitSet() works?

Programmer said...

Same one in Golang

https://github.com/pckrishnadas88/algorithms-in-golang/blob/master/how-to-find-missing-number-on-integer-array/main.go

javin paul said...

Thanks for sharing with us Krishnadas.

Abay said...

static void findMissed(int[] arr){
int num = 1;
int i = 0;
while(true){
if(arr[i] == num){
num++;
i=0;
}else{
i++;
}
if(i == arr.length){
System.out.println("missed " + num);
num++;
i=0;
}
if(num > arr.length) break;
}
}

myonline said...

Can u plz solve some problems

javin paul said...

@Unknown which problems?

Miroslav Sivon said...

for py:

nums = [x for x in range(1, 101)]
nums[75] = ''
for i, num in enumerate(nums, start=1):
if i != num:
print(i)

Unknown said...

int[] arr=new int [100];
int sum=0;
int sum1=0;
int missNum;
for(int i =0;i<arr.length;i++){
arr[i]=i+1;
System.out.print(" "+arr[i]);
sum+=arr[i];

}
System.out.println();
System.out.println("full array sum = "+sum);

missNum=((int)(1+Math.random()*100));//random missNum between 1-100
for(int j=0;j<arr.length;j++){
if(j!=missNum){
arr[j]=j+1;
System.out.print(" "+arr[j]);
sum1+=arr[j];
}
}
System.out.println();
System.out.println("missNum array sum = "+sum1);
missNum=sum-sum1;
System.out.println("misNum = "+missNum);

Unknown said...

public class Main
{
public static void main(String[] args) {
int[] arr={1,2,4,5,6,8,9,10,12,14,18};
int sum=1;
for(int i=0;i<arr.length;i++)
{
if(arr[i]!=sum)
{
System.out.println(sum);
sum++;
}
sum++;

}
}
}

Anonymous said...

import java.io.*;
import java.util.Scanner;
class e
{
void func(int[] a,int n)
{
int sum=0;
int k=n*(n+1)/2;
for(int i=0;i<n-1;i++)
{
sum=sum+a[i];
}
int miss=k-sum;
System.out.println("the missing number is"+miss);
}
public static void main(String args[])
{
e d=new e();
Scanner sb=new Scanner(System.in);
int n=sb.nextInt();
int[] a=new int[100];
for(int i=0;i<n-1;i++)
{
a[i]=sb.nextInt();
}
d.func(a,n);
}
}
this code will work out in a simple way

Satishkumar said...

public class MissingNumbersExample {

public static void main(String[] args) {
int[] arr = {1, 3, 4, 5, 7, 10};
missingNumber(arr, 10);
}
// if the array is an sorted array simple way to find missing numbers as follow
public static void missingNumber(int[] array, int count) {
int[] mn=new int[count-array.length];
int n=0;
int j = 1;
for (int i = 0; i < 10; i++) {
if (i < array.length) {
if (array[i] != j) {
mn[n]=j;
n++;
i--;
}
}
j++;
}
System.out.println("Missing numbers :"+Arrays.toString(mn));
}
}

Unknown said...

What if there is duplicates in the array?

Unknown said...

45

javin paul said...

@Unknow, if there are duplicates in array then this method will not work. for that you need to adopt a different solution using set and map, you can check the complete solution here, how to find missing numbers in array with duplicates

Maruthi said...

Easiest way to find Missing Numbers in Array
public class MissingNumberinArray {

public static void main(String[] args) {
int[] array = {1, 2, 3, 5, 7, 8};
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] != array[i] + 1) {
System.out.println("MISSING ELEMENT " + (array[i] + 1));
}
}
}
}

Unknown said...

Another little method after sorting the array :

private static void printMissingNumberConditional(int[] numbers, int count) {
Arrays.sort(numbers);
for(int i =0, j=1; i <count; i++,j++){
while(j<=count && numbers[i]!=j){
System.out.println("Missing number found : " + j);
++j;
}
}
}

javin paul said...

Nice one, keep it up.

Gunjan said...

import java.util.*;
public class Main
{
public static void main(String[] args) {
int n=10;
int arr[]={10,10,4,4,3,2,5,3,2,8,8};
int arr1[]={1,2,4,5,6,8,9,7,3,10,2,8};
System.out.println("first array");
missingNo(arr,n);
System.out.println("\nsecond array:");
missingNo(arr1,n);
}
public static void missingNo(int arr[],int n){
int b[]=new int[n];
int flag=0;
for(int i=0;i<arr.length;i++){
b[arr[i]-1]=arr[i];
}
// System.out.println(Arrays.toString(b));
for(int i=0;i<n;i++){
if(b[i]==0){
flag=1;
System.out.print(i+1+",");
}
}
if(flag==0){
System.out.println("No missing element");
}
}
}

Akshar Zala said...

The Code Below Is Best way to find any number of missing Numbers try it once.


public class Main
{
public static void main(String[] args) {
int arr[]= {1,2,3,4,5,6,7,8,9,10,11,12,14,15,17,18,19,20};
int y = 0;
int z = 0;
int a = 0;
int size = arr.length - 1;
for (int x = 0 ; x < size; x++){
y = x+1;
z = arr[y] - arr[x];
a = arr[x] + 1;
if (z==1){
continue;
}
else{
System.out.println("The Missing Number is " + a );
}
}

}
}

javin paul said...

It's actually good but can it handle multiple missing numbers?

Vigneshbuggaram said...

In c language:

int main(){
int a[ ]={1,2,3,4};
int count =0 ,flag=0;
for(int i=0; I<a.len();I++){
if(a[i]+1==a[i+1]) flag=1;
else count ++;
If(flag==1) printf(“no missing );
else printf(“no. Of missed are ;%d”,count );
return 0;
;

Nathaniel Cobbinah said...

import java.util.LinkedList;
import java.util.List;

public class missingElement {

public static void main(String[] args) {

int values[] = {17, 1, 2, 3, 4, 6, 7, 9, 8, 10 ,15,23};

int[] arrSorted = sortValues(values);
/*for(int value: arrSorted) {
System.out.println(value);
}*/

//pass sorted Array to get Missing Numbers
List results = getMissingNubmers(arrSorted);
for (int value : results) {
System.out.println(value);
}
}

public static int[] sortValues(int[] arr) {
// sort in asc first (any sort algo will do depending on the complexity you want
// going with bubble sort
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}

public static List getMissingNubmers(int[] arr) {
List missingNumbers = new LinkedList<>();
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < arr[i + 1]) {
if (arr[i + 1] - arr[i] != 1) {
int rangeLeft = arr[i + 1] - arr[i];
for(int k=1; k < rangeLeft; k++) {
missingNumbers.add(arr[i] + k);
}
}
}
}
return missingNumbers;
}

}

Post a Comment