Find missing number unsorted contiguous array coderinme

Find missing number

It is very hectic to find a missing number from an array, sometimes it is very time-consuming. But the quickest way to find a missing number in a number’s array of n-1 numbers and these numbers or integers are in the range of 1 to n. We will right the efficient optimum, readable complete solution for that to reduce our problem in such cases.
e.g.

If we are given n=6 and

the array is [6,2,4,1,5]

we can see that 3 is missing in this unsorted list. Now, the question is how we going to find it or we can say how we going to implement it in a way to find that number without any complexity.

I Method

We can use sum formula.If we know the ‘n’ value we can find the sum of ‘n’ integer by n*(n+1)/2 then we can subtract every element from the array and the remainder will be the answer.

n=6

sum=21 {6*7/2}
we can subtract 21-6= 15
15-2=13
13-4=9
9-1=8
8-5=3
so missing value is 3

#include<iostream>
using namespace std;
/* function where this method applied */
int findMissing (int a[], int n)
{
    int sum= n*(n+1)/2;   
    for (int i = 0; i< n-1; i++)
       sum-= a[i];
    return sum;
}
 
/*program  main */
int main()
{
    int n;
// range of number
    cin>>n;
    int *a=new int[n-1];
//dynamic array pf size n-1
   for(int i=0; i<n-1; i++)
      cin>>a[i];
// array element 
    int miss = findMissing(a,n);
// calling function for missing number    
cout<<miss;
   return 0;
}
II Method-modified version of Ist

In this method, we will find the sum of n numbers as well as the sum of array’s elements. after that, we will subtract them and that will be the easy and optimal solution
if we are given

n=6 and

array is [6,2,4,1,5]
so sum Of N=6*7/2=21
sum Of Elements=6+2+4+1+5=18
missingis=21-18=3

#include<iostream>
using namespace std;

/*program  main */
int main()
{
    int n,sum=0;
// range of number
    cin>>n;
    int *a=new int[n-1];
//dynamic array pf size n-1
   for(int i=0; i<n-1; i++)
{      cin>>a[i];
// array element 
sum+=a[i];
//sum of element of array
}
    int sumR=n*(n+1)/2;
   int miss=sumR-sum;
   cout<<miss;
   return 0;
}
III Method

13
downvote
We can use XOR operation which is safer than summation because in programming languages if the given input is large it may overflow and may give the wrong answer.

Before going to the solution A xor A = 0 so if we xor two identical number the value is Zero.

#include<iostream>
using namespace std;
/* function where this method applied */
int findMissing (int a[], int n)
{
    int i;
    int x1 = a[0]; /* For xor of all the elements in array */
    int x2 = 1; /* For xor of all the elements from 1 to n+1 */
     
    for (i = 1; i< n-1; i++)
        x1 = x1^a[i];
            
    for ( i = 2; i <= n; i++)
        x2 = x2^i;         
    
    return (x1^x2);
}
 
/*program  main */
int main()
{
    int n;
// range of number
    cin>>n;
    int *a=new int[n-1];
//dynamic array pf size n-1
   for(int i=0; i<n-1; i++)
      cin>>a[i];
// array element 
    int miss = findMissing(a,n);
// calling function for missing number    
cout<<miss;
   return 0;
}

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin@coderinme.com

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.