{"id":25711,"date":"2017-10-25T20:09:03","date_gmt":"2017-10-25T14:39:03","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25711"},"modified":"2017-10-25T20:09:03","modified_gmt":"2017-10-25T14:39:03","slug":"find-element-appears","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-element-appears\/","title":{"rendered":"Find the element that appears once"},"content":{"rendered":"

Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.
\nExamples:<\/strong><\/p>\n

We can use sorting to do it in O(nLogn) time. We can also use hashing, but the worst case time complexity of but hashing requires extra space.<\/p>\n

The idea is to use bitwise operators for a solution that is O(n) time and uses O(1) extra space. The solution is not easy like other XOR based solutions, because all elements appear odd number of times here. The idea is taken from here.<\/p>\n

Run a loop for all elements in array. At the end of every iteration, maintain following two values.<\/p>\n

ones: The bits that have appeared 1st time or 4th time or 7th time .. etc.<\/p>\n

twos: The bits that have appeared 2nd time or 5th time or 8th time .. etc.<\/p>\n

Finally, we return the value of \u2018ones\u2019<\/p>\n[ad type=\u201dbanner\u201d]\n

How to maintain the values of \u2018ones\u2019 and \u2018twos\u2019?
\n\u2018ones\u2019 and \u2018twos\u2019 are initialized as 0. For every new element in array, find out the common set bits in the new element and previous value of \u2018ones\u2019. These common set bits are actually the bits that should be added to \u2018twos\u2019. So do bitwise OR of the common set bits with \u2018twos\u2019. \u2018twos\u2019 also gets some extra bits that appear third time. These extra bits are removed later.
\nUpdate \u2018ones\u2019 by doing XOR of new element with previous value of \u2018ones\u2019. There may be some bits which appear 3rd time. These extra bits are also removed later.<\/p>\n

Both \u2018ones\u2019 and \u2018twos\u2019 contain those extra bits which appear 3rd time. Remove these extra bits by finding out common set bits in \u2018ones\u2019 and \u2018twos\u2019.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%20%0Aint%20getSingle(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20ones%20%3D%200%2C%20twos%20%3D%200%20%3B%0A%20%0A%20%20%20%20int%20common_bit_mask%3B%0A%20%0A%20%20%20%20%2F%2F%20Let%20us%20take%20the%20example%20of%20%7B3%2C%203%2C%202%2C%203%7D%20to%20understand%20this%0A%20%20%20%20for(%20int%20i%3D0%3B%20i%3C%20n%3B%20i%2B%2B%20)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20The%20expression%20%22one%20%26%20arr%5Bi%5D%22%20gives%20the%20bits%20that%20are%0A%20%20%20%20%20%20%20%20%20%20%20there%20in%20both%20\u2019ones\u2019%20and%20new%20element%20from%20arr%5B%5D.%20%20We%0A%20%20%20%20%20%20%20%20%20%20%20add%20these%20bits%20to%20\u2019twos\u2019%20using%20bitwise%20OR%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20Value%20of%20\u2019twos\u2019%20will%20be%20set%20as%200%2C%203%2C%203%20and%201%20after%201st%2C%0A%20%20%20%20%20%20%20%20%20%20%202nd%2C%203rd%20and%204th%20iterations%20respectively%20*%2F%0A%20%20%20%20%20%20%20%20twos%20%20%3D%20twos%20%7C%20(ones%20%26%20arr%5Bi%5D)%3B%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20XOR%20the%20new%20bits%20with%20previous%20\u2019ones\u2019%20to%20get%20all%20bits%0A%20%20%20%20%20%20%20%20%20%20%20appearing%20odd%20number%20of%20times%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20Value%20of%20\u2019ones\u2019%20will%20be%20set%20as%203%2C%200%2C%202%20and%203%20after%201st%2C%0A%20%20%20%20%20%20%20%20%20%20%202nd%2C%203rd%20and%204th%20iterations%20respectively%20*%2F%0A%20%20%20%20%20%20%20%20ones%20%20%3D%20ones%20%5E%20arr%5Bi%5D%3B%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20The%20common%20bits%20are%20those%20bits%20which%20appear%20third%20time%0A%20%20%20%20%20%20%20%20%20%20%20So%20these%20bits%20should%20not%20be%20there%20in%20both%20\u2019ones\u2019%20and%20\u2019twos\u2019.%0A%20%20%20%20%20%20%20%20%20%20%20common_bit_mask%20contains%20all%20these%20bits%20as%200%2C%20so%20that%20the%20bits%20can%20%0A%20%20%20%20%20%20%20%20%20%20%20be%20removed%20from%20\u2019ones\u2019%20and%20\u2019twos\u2019%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20Value%20of%20\u2019common_bit_mask\u2019%20will%20be%20set%20as%2000%2C%2000%2C%2001%20and%2010%0A%20%20%20%20%20%20%20%20%20%20%20after%201st%2C%202nd%2C%203rd%20and%204th%20iterations%20respectively%20*%2F%0A%20%20%20%20%20%20%20%20common_bit_mask%20%3D%20~(ones%20%26%20twos)%3B%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Remove%20common%20bits%20(the%20bits%20that%20appear%20third%20time)%20from%20\u2019ones\u2019%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20Value%20of%20\u2019ones\u2019%20will%20be%20set%20as%203%2C%200%2C%200%20and%202%20after%201st%2C%0A%20%20%20%20%20%20%20%20%20%20%202nd%2C%203rd%20and%204th%20iterations%20respectively%20*%2F%0A%20%20%20%20%20%20%20%20ones%20%26%3D%20common_bit_mask%3B%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Remove%20common%20bits%20(the%20bits%20that%20appear%20third%20time)%20from%20\u2019twos\u2019%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20Value%20of%20\u2019twos\u2019%20will%20be%20set%20as%200%2C%203%2C%201%20and%200%20after%201st%2C%0A%20%20%20%20%20%20%20%20%20%20%202nd%2C%203rd%20and%204th%20itearations%20respectively%20*%2F%0A%20%20%20%20%20%20%20%20twos%20%26%3D%20common_bit_mask%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20uncomment%20this%20code%20to%20see%20intermediate%20values%0A%20%20%20%20%20%20%20%20%2F%2Fprintf%20(%22%20%25d%20%25d%20%5Cn%22%2C%20ones%2C%20twos)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20ones%3B%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%203%2C%202%2C%203%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%20%2F%20sizeof(arr%5B0%5D)%3B%0A%20%20%20%20printf(%22The%20element%20with%20single%20occurrence%20is%20%25d%20%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20getSingle(arr%2C%20n))%3B%0A%20%20%20%20return%200%3B%0A%7D%0ARun%20on%20IDE%0AOutput%3A%0A%0A\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

2<\/pre>\n
Time Complexity: O(n)
\nAuxiliary Space: O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n
Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
\nLet us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
\nSum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
\nSum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
\nSum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
\nSum of fourth bits%3 = (1)%3 = 1;
\nHence number which appears once is 1000<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23define%20INT_SIZE%2032%0A%20%0Aint%20getSingle(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20result%0A%20%20%20%20int%20result%20%3D%200%3B%0A%20%0A%20%20%20%20int%20x%2C%20sum%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20every%20bit%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20INT_SIZE%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%20Find%20sum%20of%20set%20bits%20at%20ith%20position%20in%20all%0A%20%20%20%20%20%20%2F%2F%20array%20elements%0A%20%20%20%20%20%20sum%20%3D%200%3B%0A%20%20%20%20%20%20x%20%3D%20(1%20%3C%3C%20i)%3B%0A%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3C%20n%3B%20j%2B%2B%20)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%26%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20sum%2B%2B%3B%0A%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%2F%2F%20The%20bits%20with%20sum%20not%20multiple%20of%203%2C%20are%20the%0A%20%20%20%20%20%20%2F%2F%20bits%20of%20element%20with%20single%20occurrence.%0A%20%20%20%20%20%20if%20(sum%20%25%203)%0A%20%20%20%20%20%20%20%20result%20%7C%3D%20x%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%201%2C%2012%2C%203%2C%2012%2C%201%2C%201%2C%202%2C%203%2C%202%2C%202%2C%203%2C%207%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%20%2F%20sizeof(arr%5B0%5D)%3B%0A%20%20%20%20printf(%22The%20element%20with%20single%20occurrence%20is%20%25d%20%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20getSingle(arr%2C%20n))%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
7<\/pre>\n
<\/div>\n","protected":false},"excerpt":{"rendered":"
Find the element that appears once – Bit Algorithm – Given an array where every element occurs three times, except one element which occurs only once. Expected time complexity is O(n) and O(1) extra space.<\/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],"tags":[74856,74858,74859,74855,74853,74860,74854,74857],"class_list":["post-25711","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","tag-find-non-repeating-element-in-an-array","tag-find-non-repeating-element-in-an-array-java","tag-find-the-common-elements-of-2-int-arrays","tag-find-the-element-that-appears-once-in-a-sorted-array","tag-find-the-element-that-appears-once-java","tag-find-the-element-that-appears-once-leetcode","tag-given-an-array-of-integers-every-element-appears-twice-except-for-one","tag-there-is-an-array-with-every-element-repeated-twice-except-one-find-that-element-in-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25711","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=25711"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25711\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25711"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25711"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25711"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}