Finding the missing number in the list.

general
, , ,
1

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

2

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!

3

// 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;

}

}

4

Thanks for the help but I got it.

5

that’s good !

6

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…

7

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…

8

Mate, what r you talking about??

9

Thanks, the instructions helped

10

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

11

No problem…

12

mate , its not guaranteed it starts from 1 only.

13

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