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

Hm… interesting task. My friend from the college essay writing services would definitely help you! I will share the link with him

“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

Can you please explain?

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.

Please expalin your code.

IDK how this slipped by me. Fixed the format :smiley:

//