wu :: forums « wu :: forums - Find distinct element in array » Welcome, Guest. Please Login or Register. Nov 28th, 2024, 3:55pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Grimbal, Eigenray, ThudnBlunder, Icarus, william wu, SMQ, towr)    Find distinct element in array « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Find distinct element in array  (Read 1516 times) foobar Newbie     Posts: 7 Find distinct element in array   « on: Oct 6th, 2009, 2:16pm » Quote Modify 2N+1 elements in the array Array contains N doubles and 1 distinct   eg 1 2 3 4 3 2 1 => distinct = 4 Find the distinct element   Constraints O(1) space, O(n) time, Can't change the input array => pls dont try to sort it IP Logged nks Junior Member     Gender: Posts: 145 Re: Find distinct element in array   « Reply #1 on: Oct 7th, 2009, 12:05am » Quote Modify Hash can be used. What about range of elements?   Given link can help you   http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1214805339;start=2#2 IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Find distinct element in array   « Reply #2 on: Oct 7th, 2009, 12:17am » Quote Modify on Oct 7th, 2009, 12:05am, nks wrote: Hash can be used. No, it can't, because that wouldn't be O(1) space.     This question has been asked before, but I can't seem to find an earlier thread. It has a nice but simple solution. There is no need for additional datastructures, and the range doesn't matter. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB foobar Newbie     Posts: 7 Re: Find distinct element in array   « Reply #3 on: Oct 7th, 2009, 12:19am » Quote Modify Yes. Hash != O(1) space.   Towr, I tried a thread search before posting it but couldn't find a similar problem. You got any hints about the solution (or the whole solution itself)? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Find distinct element in array   « Reply #4 on: Oct 7th, 2009, 1:40am » Quote Modify hint 1: Make the doubles cancel each other out hint 2: You can do it using only bit-wise operators IP Logged Wikipedia, Google, Mathworld, Integer sequence DB nks Junior Member     Gender: Posts: 145 Re: Find distinct element in array   « Reply #5 on: Oct 7th, 2009, 3:44am » Quote Modify Quote: hint 1: Make the doubles cancel each other out     How can you cancel if elements are randomly ordered ?   eg 1 2 4 1 2 3 3     Quote:  hint 2: You can do it using only bit-wise operators   Can you please explain it little more?   is it like   a= XOR of SUM of elements b= XOR of all elements   c = a XOR b   Please correct me?   IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Find distinct element in array   « Reply #6 on: Oct 7th, 2009, 4:39am » Quote Modify hint 3: only one of your a, b or c above is necessary to solve the problem.   --SMQ IP Logged --SMQ foobar Newbie     Posts: 7 Re: Find distinct element in array   « Reply #7 on: Oct 7th, 2009, 6:20am » Quote Modify Yep. I got it this time.   Key hint: XOR is an associative operator.   Solution: Xor every element together. All repeats would cancel each other (since XOR is associative). Whatever would be left would be the distinct element. IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Find distinct element in array   « Reply #8 on: Oct 7th, 2009, 8:43am » Quote Modify on Oct 7th, 2009, 6:20am, foobar wrote: Key hint: XOR is an associative operator. And commutative. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB nks Junior Member     Gender: Posts: 145 Re: Find distinct element in array   « Reply #9 on: Oct 7th, 2009, 11:25am » Quote Modify Yes I got it.   Say like     a^b^c^d^a^b^c^d^e = e IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board