Author |
Topic: Duplicate Integer (Read 7133 times) |
|
nothing_
Newbie
Posts: 22
|
 |
Duplicate Integer
« on: Sep 26th, 2007, 12:35pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
nothing_
Newbie
Posts: 22
|
|
Re: Duplicate Integer
« Reply #2 on: Sep 26th, 2007, 1:03pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: Duplicate Integer
« Reply #3 on: Sep 26th, 2007, 1:09pm » |
Quote Modify
|
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: Your hint here
|
| « Last Edit: Sep 26th, 2007, 1:09pm by Aryabhatta » |
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Duplicate Integer
« Reply #4 on: Sep 26th, 2007, 2:53pm » |
Quote Modify
|
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....
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicate Integer
« Reply #5 on: Sep 26th, 2007, 3:11pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Duplicate Integer
« Reply #6 on: Sep 26th, 2007, 4:12pm » |
Quote Modify
|
@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... 
|
| « Last Edit: Sep 26th, 2007, 4:13pm by johny_cage » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicate Integer
« Reply #7 on: Sep 26th, 2007, 5:12pm » |
Quote Modify
|
on Sep 26th, 2007, 4:12pm, 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...
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Duplicate Integer
« Reply #8 on: Sep 26th, 2007, 5:43pm » |
Quote Modify
|
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.
but as u r looking the question then let find other solution for it..... 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Duplicate Integer
« Reply #9 on: Sep 26th, 2007, 5:49pm » |
Quote Modify
|
on Sep 26th, 2007, 5:43pm, 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.
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicate Integer
« Reply #10 on: Sep 27th, 2007, 12:50am » |
Quote Modify
|
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.
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
RandomSam
Newbie
Gender:
Posts: 20
|
|
Re: Duplicate Integer
« Reply #11 on: Oct 12th, 2007, 4:09pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicate Integer
« Reply #12 on: Oct 13th, 2007, 3:00am » |
Quote Modify
|
on Oct 12th, 2007, 4:09pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
satya_deep_m
Newbie
Posts: 9
|
|
Re: Duplicate Integer
« Reply #13 on: Feb 24th, 2008, 3:37am » |
Quote Modify
|
on Sep 26th, 2007, 2:53pm, 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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicate Integer
« Reply #14 on: Feb 24th, 2008, 2:54pm » |
Quote Modify
|
on Feb 24th, 2008, 3:37am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
satya_deep_m
Newbie
Posts: 9
|
|
Re: Duplicate Integer
« Reply #15 on: Feb 25th, 2008, 10:04pm » |
Quote Modify
|
on Feb 24th, 2008, 2:54pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicate Integer
« Reply #16 on: Feb 26th, 2008, 1:21am » |
Quote Modify
|
on Feb 25th, 2008, 10:04pm, 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 =  a[i] - n(n+1)/2 = A - B (where A is the repeated and B the missing number)
Y = a[i]2 - n(n+1)(2n+1)/6 = A2 - B2
Y/X = A + B
Y/X + X = 2A
Y/X - X = 2B
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Duplicate Integer
« Reply #17 on: Feb 27th, 2008, 6:49am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Duplicate Integer
« Reply #18 on: Mar 19th, 2008, 12:33am » |
Quote Modify
|
on Feb 25th, 2008, 10:04pm, 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.
|
| « Last Edit: Mar 19th, 2008, 12:34am by m_aakash » |
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Duplicate Integer
« Reply #19 on: Mar 19th, 2008, 11:30pm » |
Quote Modify
|
on Feb 26th, 2008, 1:21am, 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 = a[i] - n(n+1)/2 = A - B (where A is the repeated and B the missing number)
Y = a[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.
|
| « Last Edit: Mar 19th, 2008, 11:32pm by m_aakash » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Duplicate Integer
« Reply #20 on: Mar 20th, 2008, 1:46am » |
Quote Modify
|
on Mar 19th, 2008, 11:30pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print