# Finds the missing numbers.

Please tell me - How to finds the missing numbers from 1 to n.
I can not understand how to solve this.

Input:
int array[] = { 1, 2, 3, 4, 6, 7, 8, 9, 12 }

Output:
Missing number(s): 5, 11.

I am assuming size of that array as m and given range from 1 to n.

You can store the values of the array in a hash table, then run a loop from 1 to n and check which values are not present in the map.

Check the code here. Hope this helps.

2 Likes

Just use an array to count the frequency of each number in the initial array (i.e. amount of times each number appears in the array), and finally check of each position between 1 and N; those with counting value equal to zero are missing numbers.

Simple code:

int list[NumberOfElements+1]; //Initial list of integers…

int freq[MaxPosibleValueOfN+1]; //Array to count frequencies; positions must be initialized to zero.

for(int i = 1; i <= NumberOfElements; i++) freq[ list[i] ] ++;

for(int i = 1; i <= MaxPosibleValueOfN; i++)

if(0 == freq[i]) //then i is one missing number…

1 Like

“Just use an array to count the frequency of each number in the initial array (i.e. amount of times each number appears in the array), and finally check of each position between 1 and N; those with counting value equal to zero are missing numbers.”

-> Isn’t it a bit overkill to count each number’s apparition in the initial array ? Would not it mean going through the whole array as many time as the amount of number there is in it ?

1 Like

class Codechef
{
public static void main (String[] args)
{
int a[]={1,2,3,4,6,8,9,10,12};
int i,j;
System.out.println("\nthe missing numbers are");
for(i=0,j=1;i< a.length && j<=12;i++,j++){
if(a[i]!=j){
System.out.println("\n"+j);
i=i-1;
}
}

}
}

//THIS CODE GIVES THE SOLUTION FOR THE ABOVE PROBLEM

1 Like

Please post the code snippet using ideone.

Yes,

Given the array is : 1 2 3 4 5 6 7 8 12

Now the corresponding hash table will be :

index : Value

1 : 1
2 : 1
3 : 1
4 : 1
5 : 1
6 : 1
7 : 1
8 : 1
9 : 0
10 : 0
11 : 0
12 : 1

So now we will simply loop through the hash table and print those indices where values are zero.

No… just use the idea behind the counting sort algorithm; is linear according to the size of the initial array and maximum value of n.