Asked by SG
\nGiven an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.<\/p>\n
Method 1(Use Sorting)<\/strong> Method 2(Use XOR)<\/strong> All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets \u2013 one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.<\/p>\n Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20This%20finction%20sets%20the%20values%20of%20*x%20and%20*y%20to%20nonr-epeating%0A%20elements%20in%20an%20array%20arr%5B%5D%20of%20size%20n*%2F%0Avoid%20get2NonRepeatingNos(int%20arr%5B%5D%2C%20int%20n%2C%20int%20*x%2C%20int%20*y)%0A%7B%0A%20%20int%20xor%20%3D%20arr%5B0%5D%3B%20%2F*%20Will%20hold%20xor%20of%20all%20elements%20*%2F%0A%20%20int%20set_bit_no%3B%20%20%2F*%20Will%20have%20only%20single%20set%20bit%20of%20xor%20*%2F%0A%20%20int%20i%3B%0A%20%20*x%20%3D%200%3B%0A%20%20*y%20%3D%200%3B%0A%20%0A%20%20%2F*%20Get%20the%20xor%20of%20all%20elements%20*%2F%0A%20%20for(i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20xor%20%5E%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%2F*%20Get%20the%20rightmost%20set%20bit%20in%20set_bit_no%20*%2F%0A%20%20set_bit_no%20%3D%20xor%20%26%20~(xor-1)%3B%0A%20%0A%20%20%2F*%20Now%20divide%20elements%20in%20two%20sets%20by%20comparing%20rightmost%20set%0A%20%20%20bit%20of%20xor%20with%20bit%20at%20same%20position%20in%20each%20element.%20*%2F%0A%20%20for(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%7B%0A%20%20%20%20if(arr%5Bi%5D%20%26%20set_bit_no)%0A%20%20%20%20%20*x%20%3D%20*x%20%5E%20arr%5Bi%5D%3B%20%2F*XOR%20of%20first%20set%20*%2F%0A%20%20%20%20else%0A%20%20%20%20%20*y%20%3D%20*y%20%5E%20arr%5Bi%5D%3B%20%2F*XOR%20of%20second%20set*%2F%0A%20%20%7D%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B2%2C%203%2C%207%2C%209%2C%2011%2C%202%2C%203%2C%2011%7D%3B%0A%20%20int%20*x%20%3D%20(int%20*)malloc(sizeof(int))%3B%0A%20%20int%20*y%20%3D%20(int%20*)malloc(sizeof(int))%3B%0A%20%20get2NonRepeatingNos(arr%2C%208%2C%20x%2C%20y)%3B%0A%20%20printf(%22The%20non-repeating%20elements%20are%20%25d%20and%20%25d%22%2C%20*x%2C%20*y)%3B%0A%20%20getchar()%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Time Complexity:<\/strong> O(n) Find the two non-repeating elements in an array of repeating elements – Bit Algorithm – Given an array in which all numbers except two are repeated once.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74852,83616],"tags":[73136,70860,70814,69930,70812,70842,70843,77302,70815,73138,75509,73144,73131,75063,73152,75511,75062,75058,74830,75061,73170,73158,69959,74066,75516,70848,70855,75066,74837,74842,74835,75068,70828,74832,76933,74069,73145,75072,73155,77301,70836,72834,75059,76923,73148,73150,77303,70826,69952,74838],"class_list":["post-26130","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","category-non-repeating","tag-array-c-programming-examples","tag-array-definition-in-c","tag-array-in-c","tag-array-in-c-language","tag-array-in-c-programming","tag-array-in-c-programming-examples","tag-array-programming","tag-array-programming-questions-in-c","tag-array-programs-in-c","tag-array-programs-in-c-with-output","tag-average-in-c-programming","tag-c-array-programs","tag-c-language-array-initialization","tag-c-language-printf","tag-c-program-for-array","tag-c-program-for-average-of-5-numbers","tag-c-program-to-count-number-of-words-in-a-string","tag-c-program-using-for-loop","tag-c-programming-basics-notes","tag-c-programming-character","tag-c-programs-on-strings","tag-c-string-functions","tag-define-c-language","tag-for-loop-c-programming","tag-for-loop-c-programming-examples","tag-for-loop-in-c-programming","tag-for-loop-in-c-programming-example","tag-for-loop-programs-in-c","tag-function-c-programming","tag-function-in-c-language","tag-function-in-c-programming-examples","tag-function-program-in-c","tag-functions-in-c-programming","tag-functions-in-c-programming-with-examples","tag-how-to-input-a-string-in-c","tag-if-c-programming","tag-list-of-array-programs-in-c","tag-loop-program-in-c","tag-one-dimensional-array-in-c","tag-programming-in-c-arrays","tag-simple-c-programs-with-output","tag-string-array-in-c","tag-string-in-c-language","tag-string-programming","tag-string-programs-in-c","tag-two-dimensional-array-in-c-example","tag-types-of-array-in-c","tag-wap-in-c","tag-what-is-c-language-definition","tag-while-loop-in-c-programming-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26130"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26130\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nFirst sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn)<\/p>\n
\nLet x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.<\/p>\n xor = arr[0]^arr[1]^arr[2].....arr[n-1]<\/pre>\n
Let us see an example.\r\n arr[] = {2, 4, 7, 9, 2, 4}\r\n1) Get the XOR of all the elements.\r\n xor = 2^4^7^9^2^4 = 14 (1110)\r\n2) Get a number which has only one set bit of the xor. \r\n Since we can easily get the rightmost set bit, let us use it.\r\n set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010\r\n Now set_bit_no will have only set as rightmost set bit of xor.\r\n3) Now divide the elements in two sets and do xor of \r\n elements in each set, and we get the non-repeating \r\n elements 7 and 9. Please see implementation for this \r\n step.<\/pre>\n[ad type=\u201dbanner\u201d]\n
\nAuxiliary Space:<\/strong> O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"