{"id":8089,"date":"2021-09-30T16:00:13","date_gmt":"2021-09-30T10:30:13","guid":{"rendered":"https:\/\/python-programs.com\/?p=8089"},"modified":"2021-11-22T18:34:25","modified_gmt":"2021-11-22T13:04:25","slug":"python-program-to-find-the-missing-number-in-an-array-list","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-to-find-the-missing-number-in-an-array-list\/","title":{"rendered":"Python Program to Find the Missing Number in an array\/list"},"content":{"rendered":"
Our website provided core java programs examples with output<\/a> aid beginners and expert coders to test their knowledge gap and learn accordingly.<\/p>\n Lists in Python:<\/strong><\/p>\n Python contains a collection of built-in data types that make typical data-wrangling tasks simple. The list is one of them, a simple but useful collection type. A Python list allows you to collect Python objects in a one-dimensional row that may be accessed by position, added, removed, sorted, and subdivided.<\/p>\n Find the missing number in an array\/list of n-1 different numbers in the range of 1 to n in linear time in Python.<\/p>\n Examples:<\/strong><\/p>\n Example1:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Example2:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n There are several to find the missing number in an array\/list in python but to do the same thing in linear time we use either mathematical formula or bit manipulation techniques like below.<\/p>\n Drive into Python Programming Examples<\/a> and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.<\/p>\n Approach: <\/strong><\/p>\n The array’s length is n-1. So, using the formula n*(n+1)\/2, the sum of all n elements, i.e. the sum of numbers from 1 to n, can be determined.<\/p>\n The aim is to use the above formula to find the sum of integers between 1 and n+1, where is the size of the array. Calculate the real sum of the integers in the array as well. The difference between the two is now the missing number.<\/p>\n Algorithm:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Complexity Analysis of the above program:<\/strong><\/p>\n Time Complexity: O(n)<\/strong><\/p>\n Because only one traversal \/ one loop is needed<\/p>\n Space Complexity: O(1)<\/strong><\/p>\n Because no extra space is needed<\/p>\n To overcome the problem, this method use the XOR technique.<\/p>\n Approach:<\/strong> We know XOR cancels each other in equal numbers. This is something we can benefit from in the small range array for the missing number. Algorithm:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Complexity Analysis of the above program:<\/strong><\/p>\n Time Complexity: O(n)<\/strong><\/p>\n Because only one traversal \/ one loop is needed<\/p>\n Space Complexity: O(1)<\/strong><\/p>\n Because no extra space is needed Our website provided core java programs examples with output aid beginners and expert coders to test their knowledge gap and learn accordingly. Lists in Python: Python contains a collection of built-in data types that make typical data-wrangling tasks simple. The list is one of them, a simple but useful collection type. A Python list allows …<\/p>\ngiven list= [ 1 ,3 ,2 , 6 , 5 ]<\/pre>\n
The missing number in the given list 4<\/pre>\n
given list= [ 1 , 9 , 2 ,3 , 5 , 4 , 6 , 7 ]<\/pre>\n
The missing number in the given list 8<\/pre>\n
Program to Find the Missing Number in an array\/list in Python<\/h2>\n
\n
Method #1:Using mathematical formula<\/h3>\n
\n
def findMissingNumb(given_list):\r\n\r\n # calculating the length of the given list\r\n n = len(given_list)\r\n\r\n # Because a number is missing from the list, the real size is n+1.\r\n length = n + 1\r\n\r\n # Getting sum of all numbers from 1 to length using mathematical formula\r\n totalSum = length * (length + 1) \/ 2\r\n # calculating the sum of all elements in the given list\r\n # initializing a variable to store arraysum as 0\r\n arraysum = 0\r\n # Traversing the list\r\n for ele in given_list:\r\n arraysum = arraysum+ele\r\n\r\n # The difference between the totalsum and arraysum\r\n # of the integers in the list is the missing number.\r\n # missing number\r\n missnum = totalSum-arraysum\r\n # reeturn the missing number\r\n return int(missnum)\r\n\r\n\r\n# Driver code\r\n# given list\r\ngiven_list = [1, 3, 2, 6, 5]\r\n# passing the given list to findMissingNumb to print the missing number\r\n\r\nprint(\"The missing number in the given list\", findMissingNumb(given_list))\r\n<\/pre>\n
The missing number in the given list 4<\/pre>\n
Method #2 : Using XOR (bitwise operator )<\/h3>\n
\nCertain properties are possessed by XOR like
\nAssume a1 ^\u00a0a2^a3… a^n\u00a0= a and a1 ^a2^\u00a0a3… ^an-1 = b.
\nConsequently, a ^b = an<\/p>\n
\nThe aim is to calculate XOR for all items of the array and calculate XOR for all items from 1 through n+1. It is now the XOR between the two that is missing.<\/p>\n\n
def findMissingNumb(given_list):\r\n # calculating the length of the given list\r\n n = len(given_list)\r\n # Calculating xor of all elements in the given list\r\n totalXor = 0\r\n # Traverse the given list\r\n for i in given_list:\r\n totalXor = totalXor ^ i\r\n # calculating xor of all elements from 1 to n+1\r\n # Compute XOR of all the elements from 1 to `n+1`\r\n for i in range(1, n + 2):\r\n totalXor = totalXor ^ i\r\n # initialize the missnum with the totalXor\r\n missNum = totalXor\r\n # return the missing number\r\n return missNum\r\n\r\n\r\n# Driver code\r\n# given list\r\ngiven_list = [1, 3, 2, 6, 5]\r\n# passing the given list to findMissingNumb to print the missing number\r\n\r\nprint(\"The missing number in the given list\", findMissingNumb(given_list))\r\n<\/pre>\n
The missing number in the given list 4<\/pre>\n
\nRelated Programs<\/strong>:<\/p>\n\n