{"id":3374,"date":"2017-12-14T21:44:36","date_gmt":"2017-12-14T16:14:36","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=3374"},"modified":"2017-12-14T21:44:36","modified_gmt":"2017-12-14T16:14:36","slug":"find-element-appears-once-array-elements-occur-twice","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2017\/12\/14\/find-element-appears-once-array-elements-occur-twice\/","title":{"rendered":"Element in an array which appears once while other elements appear twice"},"content":{"rendered":"<p><b>Problem Statement<\/b> &#8211; Given an array of numbers where all numbers appear twice except for one number which appears only once, find that number.<\/p>\n<p><b>Clues<\/b> &#8211;<\/p>\n<ul>\n<li>Solution should be O(N) in time and O(1) in space.<\/li>\n<li>Use bit operations.<\/li>\n<\/ul>\n<p><b>Solution<\/b> &#8211; XOR of two same numbers is zero. So, if we take the XOR of all numbers in the array, the numbers which appear twice will get cancelled and in the end the number which is left would be our number which had appeared only once. Example &#8211;<\/p>\n<ul>\n<li>2 ^ 2 = 0<\/li>\n<li>2 ^ 2 ^ 3 = 3<\/li>\n<li>2 ^ 3 = 1<\/li>\n<li>1 ^ 2 = 3<\/li>\n<li>1 ^ 3 = 2<\/li>\n<li>2 ^ 3 ^ 2 = 3<\/li>\n<li>2 ^ 3 ^ 3 = 2<\/li>\n<\/ul>\n<p>This solution would be O(N) in time and O(1) in space.<\/p>\n<p><b>Code<\/b> &#8211;<br \/>\n<div class=\"su-tabs su-tabs-style-default su-tabs-mobile-stack\" data-active=\"1\" data-scroll-offset=\"0\" data-anchor-in-url=\"no\"><div class=\"su-tabs-nav\"><span class=\"\" data-url=\"\" data-target=\"blank\" tabindex=\"0\" role=\"button\">C<\/span><\/div><div class=\"su-tabs-panes\"><div class=\"su-tabs-pane su-u-clearfix su-u-trim\" data-title=\"C\">\n[code language=&#8221;cpp&#8221;]\nint findNonDuplicate(int arr[], int n)<br \/>\n{<br \/>\n    int xorVal = 0, i;<\/p>\n<p>    \/\/ XOR all the elements<br \/>\n    for (i = 0; i &lt; n; ++i) {<br \/>\n        xorVal ^= arr[i];<br \/>\n    }<\/p>\n<p>    return xorVal;<br \/>\n}<br \/>\n[\/code]\n<\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement &#8211; Given an array of numbers where all numbers appear twice except for one number which appears only once, find [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[16],"tags":[22],"class_list":["post-3374","post","type-post","status-publish","format-standard","hentry","category-array-interview-questions","tag-arrays-interview-questions"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=3374"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3374\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=3374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/categories?post=3374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/tags?post=3374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}