Problem Link:
CONTEST
PRACTICE
Author- Sameer Taneja
Tester- Vipin Khushu
Editorialist- Sameer Taneja
Difficulty:
Simple
Prerequisites:
Bitwise XOR
Problem:
Given an array in which all numbers except one are repeated once. (i.e. we have 2n+1 numbers and n numbers are occurring twice and remaining one have occurred once).We have to find non repeated one .
Explanation:
A Simple Solution for this problem is to run two nested loops. The outer loop picks all elements one by one and inner loop counts number of occurrences of the element picked by outer loop. If count is equal to 1 than picked element is answer and we break the loop.
Time complexity of this solution is O(n2).
The Best Solution is to do bitwise XOR of all the elements. XOR of all elements gives us odd occurring element. Please note that XOR of two elements is 0 if both elements are same and XOR of a number x with 0 is x.
xor=a[0]^ a1 ^a 2 …^a[n-1]
so.we just have to run a loop on array and do bitwise XOR of every element of array .At last XOR is equal to the answer .
eg. A[]={2,3,5,3,2}
xor=2^3^5^3^2
xor=2^2^5^3^3
xor=0^5^0
xor=5
Time complexity of this solution is O(n).
Solution
http://ideone.com/UCt763