Blog # 77 : The Lonely Element

Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once. Devise an algorithm to find the lonely element. Ex : {1 2 4 5 1 4 2} Answer : 5 courtesy: Syed Wali Hamza Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Think of some bit manipulation techniques. Hit again for solution. Solution: Note the properties of XOR : 1. A ^ A = 0 2. 0 ^ A = A 3. A ^ (B ^ C) = (A ^ B) ^ C Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice. Complexity: 1. Space: O(1) 2. Time: O(N) int lonely_element(int input[], int N){ int result=0, i=0; for(i=0; i<N; i++) result ^= input[i]; return result; }