Author |
Topic: Duplicates in Array (Read 1388 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Duplicates in Array
« on: Apr 22nd, 2007, 9:11am » |
 Quote  Modify
|
Sorry if this was posted earlier.
The following operations must be completed in linear time, constant space.
1. N different unknown values are written in the array of size 2N-1. Every value is written twice, except one. Find the unique value.
2. N different unknown values are written in the array of size 2N-2. Every value is written twice, except two. Find both unique values.
|
| « Last Edit: Apr 22nd, 2007, 10:06am by Barukh » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicates in Array
« Reply #1 on: Apr 22nd, 2007, 9:37am » |
Quote Modify
|
I am pretty sure these must have appeared before, sorry too lazy to search 
For the first one
XOR the values together. The result is the missing number
For the second one
Find the sum and sum of squares. This has overflow issues but those can be taken care of without hurting the constant spaceness or linear time
|
|
IP Logged |
|
|
|
Margit
Junior Member
Gender: 
Posts: 54
|
|
Re: Duplicates in Array
« Reply #2 on: Apr 22nd, 2007, 9:47am » |
Quote Modify
|
Sorry, do not understand this.
If you write twice (or more) to
the same location then nothing changes.
N(1) = 1
N(1) = 1
Or am I missing something ?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Duplicates in Array
« Reply #3 on: Apr 22nd, 2007, 10:05am » |
Quote Modify
|
Aryabhatta, it seems your solution is to a different problem: when the values are known.
This was not specified in the statement (I will make it explicit).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicates in Array
« Reply #4 on: Apr 22nd, 2007, 10:09am » |
Quote Modify
|
on Apr 22nd, 2007, 10:05am, Barukh wrote:Aryabhatta, it seems your solution is to a different problem: when the values are known.
This was not specified in the statement (I will make it explicit). |
|
RIght, but the solution to the first one will still not change I think.
Agreed, the second one would be incorrect (I was assuming 1...N). Sorry should have read more carefully.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicates in Array
« Reply #5 on: Apr 22nd, 2007, 10:46am » |
Quote Modify
|
on Apr 22nd, 2007, 10:09am, Aryabhatta wrote:| Agreed, the second one would be incorrect (I was assuming 1...N). Sorry should have read more carefully. |
|
Just take the XOR's and the XOR's of the squares.
[e]Or something like that...
I haven't worked out the details, you won't get the sum and sum of squares out of it, unfortunately[/e]
|
| « Last Edit: Apr 22nd, 2007, 10:51am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Duplicates in Array
« Reply #6 on: Apr 24th, 2007, 10:56pm » |
Quote Modify
|
on Apr 22nd, 2007, 10:46am, towr wrote:[e]Or something like that...
I haven't worked out the details, you won't get the sum and sum of squares out of it, unfortunately[/e] |
|
So, this remains still undone? 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicates in Array
« Reply #7 on: Apr 25th, 2007, 1:10pm » |
Quote Modify
|
Barukh, do you know the solution to this?
I don't think I will be able to get this and I have given up. Maybe a hint will help 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Duplicates in Array
« Reply #8 on: Apr 26th, 2007, 1:07am » |
Quote Modify
|
on Apr 25th, 2007, 1:10pm, Aryabhatta wrote:| Barukh, do you know the solution to this? |
|
Yes.
Quote:| I don't think I will be able to get this and I have given up. Maybe a hint will help |
|
Let me start with a small one: Begin as in #1.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Duplicates in Array
« Reply #9 on: Apr 27th, 2007, 10:05am » |
Quote Modify
|
Another hint:
After XOR-ing all the numbers, we get the XOR of two unique values. Use it as a separator of the two values.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicates in Array
« Reply #10 on: Apr 27th, 2007, 12:32pm » |
Quote Modify
|
OK. I think I have it.
Let the values in question be s and t.
We can find s XOR t = M (say).
Suppose the left most bit of M which is set to 1 is at position k+1 (counting from right)
Let X = 2k+1-1. Notice that all lower k+1 bits of X are set to 1.
Also notice that exactly one of X&s (bitwise and) and X&t is >= 2k
Now traverse that array A using index i, and if A[i] & X >= 2k, do S = S XOR A[i], else do T = T XOR A[i]
(Initialize S and T appropriately)
When we are done, S and T take the required values.
It is a nice problem, btw.
|
| « Last Edit: Apr 27th, 2007, 1:06pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Duplicates in Array
« Reply #11 on: Apr 27th, 2007, 1:05pm » |
Quote Modify
|
Very clever!
The solution might be a bit clearer if we do:
Pick k such that (S^T)&2k != 0. Then S is the xor of those A[i] for which A[i]&2k != 0, and T is the xor of the remaining A[i].
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Duplicates in Array
« Reply #12 on: Apr 27th, 2007, 3:48pm » |
Quote Modify
|
Under the assumption that the values in the array are of a known, fixed number of bits:
3. N different unknown values are written in the array of size 2N-3. Every value is written twice, except three. Find all three unique values (still in O(N) time and constant space).
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Duplicates in Array
« Reply #13 on: Apr 27th, 2007, 10:53pm » |
Quote Modify
|
Well done, Aryabhatta and Eigenray!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Duplicates in Array
« Reply #14 on: Apr 28th, 2007, 3:57am » |
Quote Modify
|
Just so no one misunderstands my winking smiley above: I believe there is a solution to the three unique value variant as well. (I haven't found a way to extend it to four yet, though. )
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicates in Array
« Reply #15 on: Apr 28th, 2007, 6:37am » |
Quote Modify
|
on Apr 27th, 2007, 3:48pm, SMQ wrote:| 3. N different unknown values are written in the array of size 2N-3. Every value is written twice, except three. Find all three unique values (still in O(N) time and constant space). |
|
Take the XOR of all numbers
If it's 0 start again with the XOR of the numbers +1
Split on whatever bit is set like before (keepign in mind whetherr you're in the normal or the +1 case), and you get a XOR of two numbers and a XOR of 1.
Try splitting both, if you get a zero in both splits, zero is one of the three numbers. In either case the rest are the non-zeros.
|
| « Last Edit: Apr 28th, 2007, 6:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicates in Array
« Reply #16 on: Apr 28th, 2007, 11:54am » |
Quote Modify
|
on Apr 27th, 2007, 3:48pm, SMQ wrote:Under the assumption that the values in the array are of a known, fixed number of bits:
3. N different unknown values are written in the array of size 2N-3. Every value is written twice, except three. Find all three unique values (still in O(N) time and constant space).
--SMQ
|
|
If the bit size is fixed of size k say.
Then we just have an array of size 2k and mark each number using 2bits. 1 for existence in the array the other for denoting if it appears twice.
This will work for any number of numbers which are not repeated, not just 3.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Duplicates in Array
« Reply #17 on: Apr 28th, 2007, 6:30pm » |
Quote Modify
|
on Apr 28th, 2007, 6:37am, towr wrote:| Split on whatever bit is set like before (keepign in mind whetherr you're in the normal or the +1 case), and you get a XOR of two numbers and a XOR of 1. |
|
Unless I'm mistaken, you could also get the XOR of all three numbers and 0, could you not?
(Arybhatta, I had in mind a bit less constant space than that )
--SMQ
|
| « Last Edit: Apr 28th, 2007, 6:32pm by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicates in Array
« Reply #18 on: Apr 29th, 2007, 7:12am » |
Quote Modify
|
on Apr 28th, 2007, 6:30pm, SMQ wrote:| Unless I'm mistaken, you could also get the XOR of all three numbers and 0, could you not? |
|
Hmm, yes, come to think of XORing in this way isn't a good way to tell if a bit in one of the numbers is different from the corresponding bits in the other two.
I suppose you could always make 32 (or however many bits in a number) passes of the array..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Duplicates in Array
« Reply #19 on: Apr 29th, 2007, 12:41pm » |
Quote Modify
|
on Apr 29th, 2007, 7:12am, towr wrote:| I suppose you could always make 32 (or however many bits in a number) passes of the array.. |
|
Stricto sensu that would make it O(n log n).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Duplicates in Array
« Reply #20 on: Apr 29th, 2007, 2:09pm » |
Quote Modify
|
on Apr 29th, 2007, 12:41pm, Grimbal wrote:| Stricto sensu that would make it O(n log n). |
|
Which is why I was careful to specify the additional assumption that values in the array be a known, fixed number of bits; making the solution O(N*k) = O(N) where k in the number of bits in a value. Your criteria of "constant storage" in the original problem(s) would appear to have the same assumption -- that, at the least, the number of bits needed to represent the largest value in the array is known before hand.
The solution I had in mind was much along the lines towr has suggested:
1) For k-bit values in the array, initialize 2k + 1 "counters" -- a0...ak-1, b0...bk-1, and x -- to 0.
2) For each element, e, in the array: x <- x XOR e; for each bit 0 <= i < k: if bit i of e == 0, ai <- ai XOR e, else bi <- bi XOR e.
3) For each bit 0 <= i < k until an answer is found: if either ai == x and bi == 0 or the other way around, nothing can be learned from bit i. Otherwise, if bit i of x is 0 then ai is one of the unknowns, and bi is the XOR of the other 2 (and a split can be performed as with 2 unknowns), else if bit i of x is 1 then bi is one of the unknowns and ai is the XOR of the other 2.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Duplicates in Array
« Reply #21 on: Apr 29th, 2007, 2:55pm » |
Quote Modify
|
Of course if the number of bits were truly bounded, so too would be N, and everything would be constant time.
Otherwise even taking the XOR of all the numbers would take at least N log N time, and keeping 2k+1 counters would technically be N(log N)2. (You could also sort them all in that much time, but not without extra space.)
I assume "constant space, linear time" really means constant number of "basic" variables and linear number of "basic" operations, which each technically take log N space and time, respectively. So really log N space, N log N time. (Or possibly (log N)1+ , in the case of multiplication, say.)
(For example, taking Product{PA[i]}, where Pk is the k-th prime, would be cheating, because even though it only uses one variable, it's not even close to constant space.)
|
| « Last Edit: Apr 29th, 2007, 2:59pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print