 # Finding the missing number in the list.

For example, I want to find a missing number in an array of continuous numbers
like, in [1,2,6,8,3,9,4,5] i want to find the missing number(7) between 1-9
I don’t understand how to write a program for it.
HALP ME

you can just sort the array and then start iterating the array and whenever you find that an element is missing push it into a vector and for query (l, r) you can just find the upper and lower _bound of this vector for l and r and then just print you answer be it count of numbers missing or the numbers itself hope it helps!

// here is my solution

#include

using namespace std;

int main()
{

``````int arr={0};  //get a array 10 length and inialize with zero.

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

int n;
cin>>n;    // take  input by user
arr[n]=arr[n]+1;   //  increase by one array at that index

}

for(int i =1;i<=9;i++)//check the every index if it is zeroo.
{

if(arr[i]==0)    //if anyone array index is zero means number is missing
cout << "missing number : " << i <<endl;

}
``````

}

Thanks for the help but I got it.

that’s good !

Well,
There are two solutions…

First…

To keep a boolean array of size (upperbound+1) and whenever you input a number from array, set array[i] = true;

After all elements of given array are processed, the missing numbers are those for which array[i] == false;

Following pseudo code

``````boolean[] found;
int[] array;     //given array
for(int i = 0;i < array.length; i++){
found[array[i]] = true;
}

for(int i = 0; i < found.length; i++){
if(found[i] == false)System.out.print(i+" ");
}
``````

Second method,
Sort the array, run the for loop from lowerbound to upperbound and binary search for current value…

Hope this helps…

To solve such problem you need to apply a little knowledge of mathematics.
Sum of Continuous Numbers from a to b, where b>=a is :-
SUM = b*(b+1)/2 - (a-1)*a/2;
Now, if you don’t know value of a and b.
Also, find SUM_Array during taking input.
Now, Missing_Number = SUM - SUM_Array;

This method is better in case of time complexity as you don’t have to iterate array again after taking input.

Mate, what r you talking about??

Thanks, the instructions helped

i’ll try it out(apparently, I don’t have enough reputation to upvote. sori:(

No problem…

mate , its not guaranteed it starts from 1 only.

sort it , traverse wherever a[i+1]-a[i]>1 , there is the number missing //