I fail to see how any of them work in the general case.
In fact, I don't even see them working with range restrictions for n. Also
what is the missing number you are talking about? The question is to find
the repeated number. As I said before, its an element uniqueness problem
whose lower bound is
@^^ many solution to this problem in O(n)
METHOD 1(Use sum formula)
Algorithm:
1. Get the sum of numbers
total = n*(n+1)/2
2 Subtract all the numbers from sum and
you will get the missing number.
Time Complexity: O(n)
METHOD 2(Use XOR)
1) XOR all the array elements, let the resu
This problem does not seem to have a O(n) time solution in the general case
because it is a version of the Element uniqueness problem (
http://en.wikipedia.org/wiki/Element_distinctness_problem) which has a
proven tight asymptotic bound of *n log n*.
On Sun, Jan 16, 2011 at 11:17 PM, awesomeandroi
if range is defined there are several methods discussed at
http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html
Regards
Priyaranjan
http://code-forum.blogspot.com
On Jan 16, 11:35 pm, yq Zhang wrote:
> @Dave, your algorithm is a dijkstra cycle finding algo. It requires the
> f
@All as mention earlier by nphard range of numbers is not defined so
we can't use method proposed by dave.and if number are between 1-n
then there are several techniques.
Regards
Priyaranjan
http://code-forum.blogspot.com
On Jan 16, 11:35 pm, yq Zhang wrote:
> @Dave, your algorithm is a dijkst
@yousaf traversing through the array and if elements have same hash
value doesn't mean that they are repeated. even two different numbers
can have same hash value,so its not guaranteed.
Regards
Priyaranjan
http://code-forum.blogspot.com
On Jan 16, 11:24 am, Yousaf wrote:
> traverse the array and
@Dave, your algorithm is a dijkstra cycle finding algo. It requires the
function to have only ONE SINGLE cycle in the transition function. However,
the transition function for the array could have several cycles. How could
you find the duplicate? Can you elaborate more on your solution? Maybe I
jus
@above
What is the purpose of A(i) regarding to the original problem about
duplicated number?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, s
Okay. Here is a further exposition of the solution. It took me a while
to remember where I had used it before.
i = n
j = n
do while not (i = j)
i = A(A((i))
j = A(j)
end
/* Now a=b can be reached at either 2k or k steps from n, */
/* where k is some integer between 1 and n. */
i = n
do whi
@Dave
Cycle finding algo (Floyd's, Brent's) can be applied only for the iterated
function values.
This means: f(x0) = x1; f(x1) = x2 and etc.
Suppose we have the following array: 1 2 3 2 4. Value 2 have two different
transitions.
Clarify your proposed method if it needs additional observations.
If the array A{1..n] contains integers in the range 1 to n-2, so that
the pigeonhole principle implies that there is at least one integer
that is duplicated in the array, then finding that duplicate entry is
equivalent to finding a node in a linked list at which a loop starts.
A solution for this p
traverse the array and hash the elements. If an element is already in
the hashtable, its repeated one.
On Jan 15, 9:21 pm, nphard nphard wrote:
> Given an array of integers of size 'n' - consisting of 'n-2' unique integers
> and 1 integer with a duplicate, find the repeated element in O(n).
>
> N
12 matches
Mail list logo
