Find the Missing Number

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Example :
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5

METHOD 1(Use sum formula)

Algorithm:

1. Get the sum of numbers
total = n*(n+1)/2
2  Subtract all the numbers from sum and
you will get the missing number.

C++

 // C++ program of above approach #include using namespace std;    class gfg {        /* getMissingNo takes array and size of array as arguments*/ public : int getMissingNo (int a[], int n) {     int i, total;     total = (n + 1) * (n + 2) / 2;      for ( i = 0; i< n; i++)         total -= a[i];     return total; } };    /*Driver code */ int main() {     gfg g;     int a[] = {1, 2, 4, 5, 6};     int miss = g.getMissingNo(a, 5);     cout << miss; }    // This code is contributed by SoM15242

C

 #include    /* getMissingNo takes array and size of array as arguments*/ int getMissingNo (int a[], int n) {     int i, total;     total  = (n+1)*(n+2)/2;        for ( i = 0; i< n; i++)        total -= a[i];     return total; }    /*program to test above function */ int main() {     int a[] = {1,2,4,5,6};     int miss = getMissingNo(a,5);     printf("%d", miss);     getchar(); }

Java

 // Java program to find missing Number    class Main {     // Function to ind missing number     static int getMissingNo (int a[], int n)     {         int i, total;         total  = (n+1)*(n+2)/2;            for ( i = 0; i< n; i++)            total -= a[i];         return total;     }             /* program to test above function */     public static void main(String args[])     {         int a[] = {1,2,4,5,6};         int miss = getMissingNo(a,5);         System.out.println(miss);        } }

Python

 # getMissingNo takes list as argument def getMissingNo(A):     n = len(A)     total = (n+1)*(n+2)/2     sum_of_A = sum(A)     return total - sum_of_A    # Driver program to test above function A = [1, 2, 4, 5, 6] miss = getMissingNo(A) print(miss) # This code is contributed by Pratik Chhajer

/div>

C#

 // C# program to find missing Number using System;    class GFG {     // Function to ind missing number     static int getMissingNo (int []a, int n)     {         int total = (n + 1) * (n + 2) / 2;                     for (int i = 0; i< n; i++)         total -= a[i];                    return total;     }            /* program to test above function */     public static void Main()     {         int []a = {1, 2, 4, 5, 6};         int miss = getMissingNo(a, 5);         Console.Write(miss);      }    }    // This code is contributed by Sam007_

PHP



Output :

3

Time Complexity : O(n)

There can be overflow if n is large. In order to avoid Integer Overflow, we can pick one number from known numbers and subtract one number from given numbers. This way we wont have Integer Overflow ever. Thanks to Sahil Rally for suggesting this improvement.

METHOD 2(Use XOR)

1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.

C++

 // C++ program to find missing Number // using xor #include using namespace std;    class gfg {        /* getMissingNo takes array and  size of array as arguments*/ public :  int getMissingNo(int a[], int n) {     int i;     int x1 = a; /* 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; i++)         x1 = x1^a[i];                    for ( i = 2; i <= n + 1; i++)         x2 = x2^i;               return (x1^x2); } };    /* Driver code */ int main() {     gfg g;     int a[] = {1, 2, 4, 5, 6};     int miss = g.getMissingNo(a, 5);     cout << miss;     getchar(); }    // This code is contributed by SoM15242

C

 #include    /* getMissingNo takes array and size of array as arguments*/ int getMissingNo(int a[], int n) {     int i;     int x1 = a; /* 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; i++)         x1 = x1^a[i];                   for ( i = 2; i <= n+1; i++)         x2 = x2^i;                    return (x1^x2); }    /*program to test above function */ int main() {     int a[] = {1, 2, 4, 5, 6};     int miss = getMissingNo(a, 5);     printf("%d", miss);     getchar(); }

Java

 // Java program to find missing Number // using xor class Main {     // Function to find missing number     static int getMissingNo (int a[], int n)     {         int x1 = a;          int x2 = 1;                     /* For xor of all the elements             in array */         for (int i = 1; i < n; i++)             x1 = x1 ^ a[i];                            /* For xor of all the elements             from 1 to n+1 */                  for (int i = 2; i <= n+1; i++)             x2 = x2 ^ i;                             return (x1 ^ x2);     }             /* program to test above function */     public static void main(String args[])     {         int a[] = {1,2,4,5,6};         int miss = getMissingNo(a,5);         System.out.println(miss);     } }

Python3

 # Python3 program to find # the mising Number # getMissingNo takes list as argument     def getMissingNo(a,n):     x1 = a     x2 = 1            for i in range(1,n):         x1 = x1 ^ a[i]                for i in range(2,n+2):         x2 = x2^i            return x1 ^ x2       # Driver program to test above function if __name__=='__main__':        a = [1, 2, 4, 5, 6]     n=len(a)     miss = getMissingNo(a,n)      print(miss)        # This code is contributed by Yatin Gupta

C#

 // C# program to find missing Number // using xor using System;    class GFG {     // Function to find missing number     static int getMissingNo (int []a, int n)     {         int x1 = a;          int x2 = 1;                     /* For xor of all the elements          in array */         for (int i = 1; i < n; i++)             x1 = x1 ^ a[i];                            /* For xor of all the elements          from 1 to n+1 */             for (int i = 2; i <= n + 1; i++)             x2 = x2 ^ i;                             return (x1 ^ x2);     }            /* driver program to test above function */     public static void Main()     {         int []a = {1, 2, 4, 5, 6};         int miss = getMissingNo(a, 5);         Console.Write(miss);     }    }    // This code is contributed by Sam007_

PHP



Output :

3

Time Complexity : O(n)