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

1 Like

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 :slight_smile:

hope it helps!

// here is my solution

#include

using namespace std;

int main()
{

int arr[10]={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;

}

}

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…

Feel free to ask anything… Please Upvote…

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.

Hope This Helped… Please UPVOTE…

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

Thanks for the help but I got it.

that’s good !

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.