wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Duplicate Integer
        
(Message started by: nothing_ on Sep 26th, 2007, 12:35pm)
Title: Duplicate Integer
Post by nothing_ on Sep 26th, 2007, 12:35pm
Given a read-only array of n integers between 1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use only O(1) space. Hint: equivalent to finding a loop in a singly linked structure.
Title: Re: Duplicate Integer
Post by Aryabhatta on Sep 26th, 2007, 12:51pm
Hint: Use search function: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1076098307;
Title: Re: Duplicate Integer
Post by nothing_ on Sep 26th, 2007, 1:03pm
The solution given there does not assume numbers to be read-only. But in this problem numbers are read-only. So how will you solve now?
Title: Re: Duplicate Integer
Post by Aryabhatta on Sep 26th, 2007, 1:09pm
There is a solution given assuming a read-only array. I believe it was by Rezyk.

Did you actually go through all the pages (i think there are 3) and come to the conclusion that that thread had no solution?

Also, when you post a problem, no matter how tough it is, please don't post a hint with it. Give people some time.

If you really think no one will get it without a hint, please use the [ h i d e ] tags.

Like this: Hint: [hide] Your hint here [/hide]
Title: Re: Duplicate Integer
Post by johny_cage on Sep 26th, 2007, 2:53pm
I have two methods for this...

Method 1
Take sum of the given array of n elements call it S1. And find sum of first n-1 numbers with the help of mathematical formula and call it S2. Now subtract S2 from S1, and you will get the duplicate number.

But this method cause overflow in some cases, as sum of n elements might result in overflow.

So, method 2 may work
Take XOR of whole array, this can be done in O(n) time. And now, take a for loop of 1 to n-1, and perform XOR again with the result... i.e.
1 XOR 2 XOR 3 XOR .... XOR n-1 XOR (earlier result)

You will get the output i.e. the duplicate number....


Hope, this will solve the purpose.
But if I am wrong... then please tell me, as mistakes makes a man perfect... ;)

Thanks....
Title: Re: Duplicate Integer
Post by Aryabhatta on Sep 26th, 2007, 3:11pm
Johny_cage,

Are you sure you read the problem correctly?

Nowhere does it say that each number appears in the array. The array could be filled with just 1 and 2...

You have solved the wrong problem.
Title: Re: Duplicate Integer
Post by johny_cage on Sep 26th, 2007, 4:12pm
@Aryabhatta

I think I read the problem very carefully... as it is written there that we have to find "a duplicate number", i.e. there is only one duplicate number. As total there are n elements and range is 1 to n-1.

Moreover, if you will say that "a duplicate number" means we have to find one duplicate from more than one duplicates, then it is incomplete question, as nowhere it is mention that elements are repeated. Clearly the question says :

Quote:
"design an O(n) time algorithm to find a duplicated integer"



Hope this will clear your doubt... :P
Title: Re: Duplicate Integer
Post by Aryabhatta on Sep 26th, 2007, 5:12pm

on 09/26/07 at 16:12:01, johny_cage wrote:
Moreover, if you will say that "a duplicate number" means we have to find one duplicate from more than one duplicates, then it is incomplete question, as nowhere it is mention that elements are repeated. Clearly the question says :


"a" means one, "the" means the only one.

Also, if you have n numbers each between 1 and n-1, don't you think there will be repetition? There is no need to explicitly state that there will be duplicate...
Title: Re: Duplicate Integer
Post by johny_cage on Sep 26th, 2007, 5:43pm
ok chill down....

let stop this issue here only....

but one thing i want to say, my solution work for the question really means that is a duplicate integer. :P

but as u r looking the question then let find other solution for it..... :)
Title: Re: Duplicate Integer
Post by Aryabhatta on Sep 26th, 2007, 5:49pm

on 09/26/07 at 17:43:17, johny_cage wrote:
ok chill down....

let stop this issue here only....

but one thing i want to say, my solution work for the question really means that is a duplicate integer. :P

but as u r looking the question then let find other solution for it..... :)


LOL! Don't worry, I am not getting worked up.

Anyway, this is the last time I will try to convince you, promise...

Care to explain how the hint which was given by the poster of the problem is relevant?
Title: Re: Duplicate Integer
Post by towr on Sep 27th, 2007, 12:50am
In any case a solution for the problem where there may be multiple duplicates will also solve the case where there is precisely one duplicate.

[hide]Consider the array a linked list where you move from a[i] to a[a[i]
Eventually you have to enter a cycle, because you move to the same position from duplicates. So as stated, it's equivalent to finding a loop in a singly linked structure.[/hide]
Title: Re: Duplicate Integer
Post by RandomSam on Oct 12th, 2007, 4:09pm
Surely a loop doesn't imply duplicate numbers: if a[1]=3, a[2]=2, a[3]=1 then there are two loops in your linked list but no duplicates.  Perhaps I am misunderstanding the idea of linked lists?
Title: Re: Duplicate Integer
Post by towr on Oct 13th, 2007, 3:00am

on 10/12/07 at 16:09:44, RandomSam wrote:
Surely a loop doesn't imply duplicate numbers: if a[1]=3, a[2]=2, a[3]=1 then there are two loops in your linked list but no duplicates.  Perhaps I am misunderstanding the idea of linked lists?
Well, it is given that there are duplicates; so the question is not whether a loop implies that there are duplicates but whether it helps you find any. (But that distinction is perhaps not all that relevant here)
If we also include a[4]=4 and a[5]=4, then clearly while we have a duplicate we won't find it by moving through the first loop. It only works when you have a figure six, i.e. when you don't loop back to where you started.
Title: Re: Duplicate Integer
Post by satya_deep_m on Feb 24th, 2008, 3:37am

on 09/26/07 at 14:53:04, johny_cage wrote:
I have two methods for this...

Method 1
Take sum of the given array of n elements call it S1. And find sum of first n-1 numbers with the help of mathematical formula and call it S2. Now subtract S2 from S1, and you will get the duplicate number.

But this method cause overflow in some cases, as sum of n elements might result in overflow.


Could you please explain how would this method work. I was trying it out as below:
Let's say the array is 1,2,4,4,5
Here I have '4' repeating in the array. Per your method, the sum of array is 1+2+4+4+5=16

So S1=16

Also sum for first n-1 numbers i.e. 4 here = 4*5/2=10

So S2=10

Now S1-S2=16-10=6, which means 6 is the duplicate number. But actually '4' is the duplicate number here. Could somebody enlighten me, what I am missing here

::)
Title: Re: Duplicate Integer
Post by towr on Feb 24th, 2008, 2:54pm

on 02/24/08 at 03:37:43, satya_deep_m wrote:
Could you please explain how would this method work. I was trying it out as below:
Let's say the array is 1,2,4,4,5
5 isn't smaller than 5, so it can't be in an array of length 5.


Let's try 1,2,4,4,3
sums to 14
1..4 sums to 10
14-10 = 4, and this is the repeated number.

Or let's try 1,2,4,4,5,3
sums to 19
1..5 sums to 15
19-15=4, and this is indeed the repeated number.


If you have numbers 1..n-1 plus x as the repeated number then the total array sums to (n-1)n/2+x, subtract (n-1)n/2 and you get x.
Title: Re: Duplicate Integer
Post by satya_deep_m on Feb 25th, 2008, 10:04pm

on 02/24/08 at 14:54:12, towr wrote:
If you have numbers 1..n-1 plus x as the repeated number then the total array sums to (n-1)n/2+x, subtract (n-1)n/2 and you get x.


ohhk..I missed the point that the array is 1...n-1 i.e. if some element is repeating, its the largest element of the array that is left out.

But, say we did not have this restriction i.e. I have an array of length n with some element repeating like 1,2,4,4,5. In this case, how should I find the repeating element in the best possible way.
Title: Re: Duplicate Integer
Post by towr on Feb 26th, 2008, 1:21am

on 02/25/08 at 22:04:04, satya_deep_m wrote:
But, say we did not have this restriction i.e. I have an array of length n with some element repeating like 1,2,4,4,5. In this case, how should I find the repeating element in the best possible way.
Well, in that case you have and an element missing, and an element repeating. So you need to find two numbers, rather than one.

One solution is to use the sum and sum of squares
X = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifa[i] - n(n+1)/2 = A - B  (where A is the repeated and B the missing number)
Y = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifa[i]2 - n(n+1)(2n+1)/6 = A2 - B2
Y/X = A + B
Y/X + X = 2A
Y/X - X = 2B
Title: Re: Duplicate Integer
Post by mad on Feb 27th, 2008, 6:49am
If I am not wrong, we solve it as in the case of a linked list , keeping two "pointers" a[i] and a[a[i] and increment them by one and two respectively till they become same, right?
Title: Re: Duplicate Integer
Post by m_aakash on Mar 19th, 2008, 12:33am

on 02/25/08 at 22:04:04, satya_deep_m wrote:
ohhk..I missed the point that the array is 1...n-1 i.e. if some element is repeating, its the largest element of the array that is left out.

But, say we did not have this restriction i.e. I have an array of length n with some element repeating like 1,2,4,4,5. In this case, how should I find the repeating element in the best possible way.


We can find both repeating and missing numbers in O(n) time and using xor trick. assuming that array boundaries from 1 to n.

step-1: xor all the array elements along with all the elements from 1 to n. the result will be xor of repeated element and missing element .

step-2: find the righmost nonzero bit position in the result from step-1.

step-3: partition the array elements and elements from 1 to n based on the bit poisition from step-2.

step-4: the xor of two partitions respectively produce repeating and missing elements.


Note: while implementing we dont have to allocate space for partitions instead we can compute it on the fly.
Title: Re: Duplicate Integer
Post by m_aakash on Mar 19th, 2008, 11:30pm

on 02/26/08 at 01:21:13, towr wrote:
Well, in that case you have and an element missing, and an element repeating. So you need to find two numbers, rather than one.

One solution is to use the sum and sum of squares
X = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifa[i] - n(n+1)/2 = A - B  (where A is the repeated and B the missing number)
Y = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifa[i]2 - n(n+1)(2n+1)/6 = A2 - B2
Y/X = A + B
Y/X + X = 2A
Y/X - X = 2B


There is a chance of overflow with the addition or multiplication. towr, how about the idea i have given above.
Title: Re: Duplicate Integer
Post by towr on Mar 20th, 2008, 1:46am

on 03/19/08 at 23:30:54, m_aakash wrote:
There is a chance of overflow with the addition or multiplication.
You can use a big-int library where it's a realistic worry.


Quote:
towr, how about the idea i have given above.
Seems good.


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