Discussion:
Duplicate in an array
(too old to reply)
sourav
2010-10-05 11:41:49 UTC
Permalink
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mukesh Gupta
2010-10-06 10:50:57 UTC
Permalink
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
tech rascal
2010-10-06 11:08:18 UTC
Permalink
can u do dis problem in linear time, o(n)??
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Anirvana Mishra
2010-10-06 12:25:20 UTC
Permalink
It can be done in linear time.
Simply take the XOR of all the elements of the array and you have the
answer now ;)
Post by tech rascal
can u do dis problem in linear time, o(n)??
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Dave
2010-10-06 13:02:10 UTC
Permalink
@Anirvana: Please demonstrate how your algorithm works on the data 1,
2, 2, 3, 5.

Dave
Post by Anirvana Mishra
It can be done in linear time.
Simply take the XOR of all the elements of the array and you have the
answer now ;)
Post by tech rascal
can u do dis problem in linear time, o(n)??
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mukesh Gupta
2010-10-06 13:09:35 UTC
Permalink
@anirvana: Your solution works for the case when all elements except
1 are repeated twice.
Here only once element is repeated twice.
Post by Dave
@Anirvana: Please demonstrate how your algorithm works on the data 1,
2, 2, 3, 5.
Dave
Post by Anirvana Mishra
It can be done in linear time.
Simply take the XOR of all the elements of the array and you have the
answer now ;)
Post by tech rascal
can u do dis problem in linear time, o(n)??
On Wed, Oct 6, 2010 at 4:20 PM, Mukesh Gupta
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.com>
.
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.com>
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-06 14:57:42 UTC
Permalink
yes, it can be done in O(n).

think about the logic working behind bucket sort.
we assume in this problem, memory space is inf
all you need to do is put all numbers in its own "bucket"
when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.
when you run to n-1 number, you know all the numbers so far are
unique(coz duplication hadn't happened). by definition of the
problem,
you have only one duplicated number. therefore, the last number is
duplicated.
O(2(n-1)) > O(n)
Post by tech rascal
can u do dis problem in linear time, o(n)??
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Ankit Singh
2010-10-06 11:47:55 UTC
Permalink
keep inserting the values as key in a hashmap where corresponding value
represents no of occurrence of key.
Break if count ==2.
Time O(n) .
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
sourav
2010-10-06 11:02:01 UTC
Permalink
@Mukesh

Thanks for your attempt. But the question asks for liner or sublinear
solution.

Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mukesh Gupta
2010-10-06 15:47:35 UTC
Permalink
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not known we cannot predict whether the algo will run in linear
time.
Any other idea for O(n)??


Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-06 17:41:06 UTC
Permalink
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of "bucket"
logic.
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not known we cannot predict whether the algo will run in linear
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mridul Malpani
2010-10-10 12:21:32 UTC
Permalink
can this problem be solved in O(n) time and in O(1) space?
Post by ligerdave
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of "bucket"
logic.
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not known we cannot predict whether the algo will run in linear
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
nishaanth
2010-10-15 16:53:49 UTC
Permalink
@ankit and lingerdave.... How does hashing help here ?? i say we have to
create an array size which is there
range of the numbers...else it cant be solved in O(n)

Hashing is not helpful here in worst case hashing may lead to a O(n2)
solution as all the keys may hash into the same place

eg.. 4,14,24,34,44,4

if h(n)= n mod 100
Post by Mridul Malpani
can this problem be solved in O(n) time and in O(1) space?
Post by ligerdave
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of "bucket"
logic.
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of
the
Post by ligerdave
Post by Mukesh Gupta
numbers is not known we cannot predict whether the algo will run in
linear
Post by ligerdave
Post by Mukesh Gupta
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you
get
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate
number in
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
Post by sourav
linear or sub linear time.
--
You received this message because you are subscribed to the
Google
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google
Groups
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
nishaanth
2010-10-15 16:54:40 UTC
Permalink
correction about that example h(n)= n mod 10
Post by nishaanth
@ankit and lingerdave.... How does hashing help here ?? i say we have to
create an array size which is there
range of the numbers...else it cant be solved in O(n)
Hashing is not helpful here in worst case hashing may lead to a O(n2)
solution as all the keys may hash into the same place
eg.. 4,14,24,34,44,4
if h(n)= n mod 100
Post by Mridul Malpani
can this problem be solved in O(n) time and in O(1) space?
Post by ligerdave
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of "bucket"
logic.
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range
of the
Post by ligerdave
Post by Mukesh Gupta
numbers is not known we cannot predict whether the algo will run in
linear
Post by ligerdave
Post by Mukesh Gupta
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or
sublinear
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you
get
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number
is
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
Post by sourav
repeated. Rest all are present only once. Find the duplicate
number in
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
Post by sourav
linear or sub linear time.
--
You received this message because you are subscribed to the
Google
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
.
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
Post by sourav
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google
Groups
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Harshal
2010-10-15 18:36:36 UTC
Permalink
let arr is given array of size N.

find the max_number in arr. O(n)

form an aux array of size_max

initiaize all elemnts of aux to 0. O(n)

for(i=0;i<N;i++) O(n)
if(aux[arr[i]]>0)
return arr[i]; //duplicate element
else
aux[arr[i]]=i+1;

the solution requires extra memory.

pls correct me if i am wrong.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
nishaanth
2010-10-15 19:18:35 UTC
Permalink
@Harshal...it aint O(n)...initiaize all elemnts of aux to 0. This can be
even o(n^2) depending on the range....
Post by Harshal
let arr is given array of size N.
find the max_number in arr. O(n)
form an aux array of size_max
initiaize all elemnts of aux to 0. O(n)
for(i=0;i<N;i++) O(n)
if(aux[arr[i]]>0)
return arr[i]; //duplicate element
else
aux[arr[i]]=i+1;
the solution requires extra memory.
pls correct me if i am wrong.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-16 22:44:44 UTC
Permalink
@nishaanth

hashing=O(n^2)? what kinda of hashing are we talking about?

array w/ range of the numbers? you meant smallest and the biggest?
so you have to scan through the given numbers first to find the range.
if you scanned, why not find the duplication in the first place?

okay, lets say you are given the smallest and the biggest. 4 and 44,
you would have an array size that's more than the size of given
numbers. what if the given set is 1, 1000000, 1?
Post by nishaanth
@ankit and lingerdave.... How does hashing help here ?? i say we have to
create an array size which is there
range of the numbers...else it cant be solved in O(n)
Hashing is not helpful here in worst case hashing may lead to a O(n2)
solution as all the keys may hash into the same place
eg.. 4,14,24,34,44,4
if h(n)= n mod 100
Post by Mridul Malpani
can this problem be solved in O(n) time and in O(1) space?
Post by ligerdave
@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of "bucket"
logic.
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of
the
Post by ligerdave
Post by Mukesh Gupta
numbers is not known we cannot predict whether the algo will run in
linear
Post by ligerdave
Post by Mukesh Gupta
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you
get
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate
number in
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Post by Mukesh Gupta
Post by sourav
linear or sub linear time.
--
You received this message because you are subscribed to the
Google
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google
Groups
Post by ligerdave
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-16 22:38:44 UTC
Permalink
@Mukesh what's not known? in the problem, it stated "an array of
positive numbers"
Post by Mukesh Gupta
@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
numbers is not known we cannot predict whether the algo will run in linear
time.
Any other idea for O(n)??
Mukesh Gupta
Delhi College of Engineering
Post by sourav
@Mukesh
Thanks for your attempt. But the question asks for liner or sublinear
solution.
Sourav
Post by Mukesh Gupta
Keep inserting elements in a binary search tree and break once you get
the find the element in the tree.
Complexity=O(n log n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google
Groups
Post by Mukesh Gupta
Post by sourav
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
Post by Mukesh Gupta
Post by sourav
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mukesh Gupta
Delhi College of Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-06 14:55:52 UTC
Permalink
yes, think about the logic working behind bucket sort.

we assume in this problem, memory space is inf

all you need to do is put all numbers in its own "bucket"

when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.

when you run to n-1 number, you know all the numbers so far are
unique(coz duplication hadn't happened). by definition of the problem,
you have only one duplicated number. therefore, the last number is
duplicated.

O(2(n-1)) > O(n)
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
juver++
2010-10-17 07:24:42 UTC
Permalink
You should use bitset.
Space complexity is O(MaxValue/8).
Time complexity is O(n + MaxValue / 32).
Post by sourav
You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Asquare
2010-10-20 10:35:03 UTC
Permalink
@juver++ - could u plz elaborate..
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
juver++
2010-10-20 12:16:07 UTC
Permalink
Use C++ bitset class. It requires O(MaxValue / 8) bytes to represent
set of integers with maximum number is MaxValue.
To find repeated number:
Iterate over the array. For each number check if it is already
inserted into a bitset.
If yes, then we find duplicated element. Otherwise, insert current
number into a set (simply set up appropriate bit in the bitset).
This approach is O(n).
Post by Asquare
@juver++ - could u plz elaborate..
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Asquare
2010-10-20 10:44:36 UTC
Permalink
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
juver++
2010-10-20 12:19:10 UTC
Permalink
Suggested approach by Anirvana doesn't work for this problem.
It's ok if array contain numbers that are repeated twice except one
element and we need to find it.
For this version solution is simple - iterate over elements and find
it's XOR value, so result = a[0] XOR a[1] ... XOR a[n - 1].
Resulted value is an element which presented only once in the array.
It works because of a property of XOR operation - a XOR a = 0 (so
repeated twice pairs disappeared).
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
ligerdave
2010-10-20 21:42:07 UTC
Permalink
what if two elements are not next to each other. would it work?
Post by juver++
Suggested approach by Anirvana doesn't work for this problem.
It's ok if array contain numbers that are repeated twice except one
element and we need to find it.
For this version solution is simple - iterate over elements and find
it's XOR value, so result = a[0] XOR a[1] ... XOR a[n - 1].
Resulted value is an element which presented only once in the array.
It works because of a property of XOR operation - a XOR a = 0 (so
repeated twice pairs disappeared).
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mahesh_JNU
2010-10-20 10:49:35 UTC
Permalink
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its complexity
is O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mahesh Giri
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Dave
2010-10-21 02:26:02 UTC
Permalink
@Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0.
But the duplicate element is 4, not (14-0) / 2 = 7.

Dave
Post by Mahesh_JNU
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its complexity
is  O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
   Mahesh Giri
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
karthik asok
2010-10-21 04:30:12 UTC
Permalink
Considering sequence 1, 2, 3, 4, 4 and n = 5
lets have missing number as X and repeated number as Y.

(1*2*3*4*4)/n! = 4/5=Y/X => 5Y = 4X => Y=4X/5

(sum of all numbers) + X - Y = n(n+1)/2.
14 + X - Y = 15
X-4X/5=1

X = 5 ---> missing value is 5.
Y = 4 --> repeated value.
Post by Dave
@Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0.
But the duplicate element is 4, not (14-0) / 2 = 7.
Dave
Post by Mahesh_JNU
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its
complexity
Post by Mahesh_JNU
is O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google
Groups
Post by Mahesh_JNU
Post by Asquare
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Mahesh Giri
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks & Regards,
Karthik
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Dave
2010-10-21 04:41:26 UTC
Permalink
@Karthik: There was no requirement that the numbers be between 1 and
n. Only positive and one number is repeated. So 1, 9, 11, 1 also is
valid input, with expected output 1.

Dave
Post by karthik asok
Considering sequence 1, 2, 3, 4, 4 and n = 5
lets have missing number as X and repeated number as Y.
(1*2*3*4*4)/n! = 4/5=Y/X => 5Y = 4X => Y=4X/5
(sum of all numbers) + X - Y = n(n+1)/2.
14 + X - Y = 15
X-4X/5=1
X = 5 ---> missing value is 5.
Y = 4 --> repeated value.
Post by Dave
@Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0.
But the duplicate element is 4, not (14-0) / 2 = 7.
Dave
Post by Mahesh_JNU
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its
complexity
Post by Mahesh_JNU
is  O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google
Groups
Post by Mahesh_JNU
Post by Asquare
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
 > > .
Post by Mahesh_JNU
Post by Asquare
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
   Mahesh Giri
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks & Regards,
Karthik- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
MOHIT ....
2010-10-21 03:04:46 UTC
Permalink
i = array[0];

while (array[i] != 0) {

int temp = array[i];

array[i] = 0;
i=temp;
}

return i;

i think this will also work with o(n) time and o(1) complexity.....
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
MOHIT ....
2010-10-21 03:08:55 UTC
Permalink
above will work only if num of element in array > max value in array else
we have to use auxilary array.....
as suggested above ...
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Dave
2010-10-21 19:21:47 UTC
Permalink
@Mohit: But what if the array is of length 3 and the elements are 1,
10000, 1?

Dave
Post by MOHIT ....
i = array[0];
while (array[i] != 0) {
    int temp = array[i];
    array[i] = 0;
    i=temp;
}
return i;
i think this will also work with o(n) time and o(1) complexity.....
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
MOHIT ....
2010-10-21 19:25:37 UTC
Permalink
@ dev : i said eariler it work only if max number is less than no of values
in array ...
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
juver++
2010-10-21 16:36:47 UTC
Permalink
Are you kidding?
Did you test your solution?

Suppose, A = {1, 4, 5, 6, 2, 2}.
Sum of the elements is S=20, X_SUM = 6.
Result of your algo is (20-6)/2=7 instead if correct 2.
Post by Mahesh_JNU
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its complexity
is  O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
   Mahesh Giri
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Mridul Malpani
2010-10-22 16:59:04 UTC
Permalink
@ mahesh

i didnt get ur algo. why it will work??
plz expalin..
Post by Mahesh_JNU
Just add the number of the array and let the sum is S. Its complexity is
O(n).
Now XOR all elements of the array and say the result is X_SUM.Its complexity
is  O(n).
Now the duplicate element is = (S - X_SUM)/2
Post by Asquare
@Anirvana - In context to the XOR method u suggested, could u plz
explain why does it so happen.. ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group, send email to
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
   Mahesh Giri
--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org
To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Continue reading on narkive:
Loading...