{"id":8096,"date":"2021-09-30T16:00:38","date_gmt":"2021-09-30T10:30:38","guid":{"rendered":"https:\/\/python-programs.com\/?p=8096"},"modified":"2021-11-22T18:34:25","modified_gmt":"2021-11-22T13:04:25","slug":"python-program-to-find-the-odd-occurring-element-in-an-array-list","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-to-find-the-odd-occurring-element-in-an-array-list\/","title":{"rendered":"Python Program to Find the Odd Occurring Element in an Array\/list"},"content":{"rendered":"
Are you new to the java programming language? We recommend you to ace up your practice session with these Basic Java Programs Examples<\/a><\/p>\n Given a list which contains all duplicate elements (each element occurs even times) except one element we have to find the odd occurring element.<\/p>\n Given a array\/list the task is to print the odd occurring element in the given list.<\/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 ways to find the odd occurring element in an array .<\/p>\n The first thought is to run two loops and use the count to determine the frequency of the items.<\/p>\n If the count is one, the element is the odd one out in the specified array\/list.<\/p>\n But this approach takes two loops. This approach therefore requires O(n^2) time complexity.<\/p>\n This program is therefore not an efficient way.<\/p>\n We will look at the efficient approaches 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 We can use hashing to solve this problem in O(n) time for an input containing elements. We start by traversing the array and keeping track of the frequency of each entry in a hash table. Then, after processing each array element, return the element with the odd frequency. The drawback with this strategy is that it also need O(n) more space. It also necessitates one array traverse and one hash table traversal.<\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Complexity analysis of the above approach :<\/strong><\/p>\n Time Complexity : O( n)<\/strong><\/p>\n Since hashing requires max of O(n) Time Complexity<\/p>\n Space Complexity : O(n)<\/strong><\/p>\n Since it requires extra space<\/p>\n We can solve this problem\u00a0during a\u00a0<\/span>single traversal of the array and constant space. The idea is to use the XOR operator. We know that if we XOR\u00a0of a number <\/span>with itself an odd number of times, the\u00a0result’s\u00a0<\/span>the amount\u00a0<\/span>itself; otherwise, if we XOR of a number<\/span>\u00a0<\/span>a even <\/span>number of times with itself, the\u00a0result’s\u00a0<\/span>0. Also, the XOR of a number<\/span>\u00a0<\/span>with 0\u00a0is usually\u00a0<\/span>the amount\u00a0<\/span>itself.<\/p>\n So, if we take XOR of all array elements, even appearing elements will cancel each other, and we are left with the only odd appearing element.<\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Complexity analysis of the above approach :<\/strong><\/p>\n Time Complexity : O( n)<\/strong><\/p>\n Since it requires only one Traversal<\/p>\n Space Complexity : O(1)<\/strong><\/p>\n Since it doesn’t requires any extra space<\/p>\n Related Programs<\/strong>:<\/p>\n Are you new to the java programming language? We recommend you to ace up your practice session with these Basic Java Programs Examples Given a list which contains all duplicate elements (each element occurs even times) except one element we have to find the odd occurring element. Given a array\/list the task is to print …<\/p>\ngiven list = [\u00a0 3 , 5, 4 ,1 ,4 ,8 ,5 , 1 ,3]<\/pre>\n
The odd occurring number in the given list 8<\/pre>\n
given list = [ 1 , 4 ,2 ,4 ,1]<\/pre>\n
The odd occurring number in the given list 2<\/pre>\n
Program to Find the Odd Occurring Element in an Array\/list in Python<\/h2>\n
\n
Method #1:Using Hashing<\/h3>\n
\n
# importing counter from collections\r\nfrom collections import Counter\r\n# function which returns the odd occuring element in the given list\r\n\r\n\r\ndef findOddNumb(given_list):\r\n # Calculating the frequency of all elements using Counter() function\r\n frequency = Counter(given_list)\r\n # Traversing the frequency dictionary\r\n for key in frequency:\r\n # checking the value if it is 1\r\n if(frequency[key] == 1):\r\n # return the element\r\n return key\r\n\r\n\r\n# Driver code\r\n# given list\r\ngiven_list = [3, 5, 4, 1, 4, 8, 5, 1, 3]\r\n# passing the given list to findOddNumb to print the odd occuring number\r\n\r\nprint(\"The odd occuring number in the given list\", findOddNumb(given_list))\r\n<\/pre>\n
The odd occurring number in the given list 8<\/pre>\n
Method #2:Using XOR(Bitwise Operator)<\/h3>\n
# importing counter from collections\r\nfrom collections import Counter\r\n# function which returns the odd occuring element in the given list\r\n\r\n\r\ndef findOddNumb(given_list):\r\n # Taking a variable xorEle and initialize it with 0\r\n xorEle = 0\r\n # Traversing the given list\r\n for ele in given_list:\r\n xorEle = xorEle ^ ele\r\n\r\n # return the odd occuring element\r\n return xorEle\r\n\r\n\r\n# Driver code\r\n# given list\r\ngiven_list = [3, 5, 4, 1, 4, 8, 5, 1, 3]\r\n# passing the given list to findOddNumb to print the odd occuring number\r\n\r\nprint(\"The odd occuring number in the given list\", findOddNumb(given_list))\r\n<\/pre>\n
The odd occurring number in the given list 8<\/pre>\n
\n