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.

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.

#Note : the numbers are not in sorted order


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.
 
 
Note : Time complexity is O(n);
 




Algorithm : Using EX-OR




Here we can use same concept of finding which element is odd number times in the given list.






  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.






































Comments











Post a Comment























Popular posts from this blog









 How to swap two numbers without using a temporary variable?





















   method 1:         #include <stdio.h>   int  main()   {      int  x = 10, y = 5;          // Code to swap 'x' and 'y'      x = x + y;  // x now becomes 15      y = x - y;  // y becomes 10      x = x - y;  // x becomes 5          printf ( "After Swapping: x = %d, y = %d" , x, y);          return  0;   }               Method 2 (Using Bitwise XOR)             #include <stdio.h>   int  main()   {      int  x = 10, y = 5;          // Code to swap 'x' (1010) and 'y' (0101)      x = x ^ y;  // x now becomes 15 (1111)      y = x ^ y;  // y becomes 10 (1010)      x = x ^ y;  // x becomes 5 (0101)          printf ( "After Swapping: x = %d, y = %d" , x, y);          return  0;   }         








Read more










Write a program to reverse a string?





















  Algorithm 1 using stack :   1) Create an empty stack. 2) One by one push all characters of string to stack. 3) One by one pop all characters from stack and put     them back to string.              Algorithm 2 using array:     1. here we have to swap the elements                  








Read more