Possible Duplicate:
Find a special number in an array
Given an array that contains all elements thrice except one. Find the element which occurs once. Time complexity- O(n). Space complexity- O(1).
Eg. ar[10]={1,2,1,2,5,5,5,7,1,2}. ans= 7.
Asked
Active
Viewed 1,477 times
4
-
1Have you tried anything? ...and is this homework? – nbrooks Jul 18 '12 at 02:41
-
1This has been asked very similarly as: http://stackoverflow.com/questions/4772561/number-which-occurs-only-once-in-the-array – Nick Jul 18 '12 at 02:42
-
I have tried but couldn't solve with given complexity. – Manish Jul 18 '12 at 02:43
-
@Nick: They are different problems. – nhahtdh Jul 18 '12 at 02:44
-
@Nick.Also XOR won't work here. – Manish Jul 18 '12 at 02:44
-
@Blender.I have only slutions in mind but they don't follow up complexity.One is to sort it and then check adjacent elemnts. Second is to do Hashing. – Manish Jul 18 '12 at 02:55
-
2Have a look at this answer: http://stackoverflow.com/a/5208533/622391 – Simon MᶜKenzie Jul 18 '12 at 03:13
-
@Kay i have 1 processor only. – Manish Jul 18 '12 at 03:22
-
@SimonMcKenzie -- i think that's exactly what i want!!. thanks. But will it not overflow, if i give inputs in order like 1,2,3,4,5,6,7..., 3,2,1 ? – Manish Jul 18 '12 at 03:25
-
Actually, the linked answer may do it. O_o – Kijewski Jul 18 '12 at 03:27
-
2That answer is horribly written, though. Can't understand what's going on... – nhahtdh Jul 18 '12 at 03:28
-
1There is a nice explanation of the answer here http://shashank7s.blogspot.de/2011/03/wap-for-find-one-elements-which-occurs.html – PermanentGuest Jul 18 '12 at 11:17