point to note abt anand's code
reason why it does not work
a] when u r doing xor from index 1 to index n( take two cases that n/2
is od or even)
resulting xor will be an xor impression of non repeating number +
either 0 or 1 time the repeating number
now you start xoring again from index
how about using hashing???
at the first collision we will know the repeated element
worst case time here will be ( n/2 +1 )
On Fri, Aug 6, 2010 at 12:04 AM, Anand anandut2...@gmail.com wrote:
http://codepad.org/8eDVyeBT
Using XOR logic we can find Duplicates in O(n)
On Thu, Aug 5,
Using median, you can do it!
Thanks,
Sathaiah
On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote:
an array in which n/2 elements are unique...and the remaning n/2 have
the same elements but reapeated n/2 times. can anyone suggest a linear
solution with constant space/...
no the array is unsorted..
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote:
If I understand the question correctly... there is an array of size n which
has n/2 distinct elements and one element is repeated n/2 times.
For e.g.:
n = 4: 1 2 3 3
n = 61 2 3 4
Hey Anand,
Can you(or anyone who understood it) elaborate on that XOR logic idea of
yours?
Thanks,
Seckin
On Fri, Aug 6, 2010 at 7:14 AM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
no the array is unsorted..
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote:
If
hi anand.. can u write up a pseudocode of ur algorithm using XOR logic
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please elaborate ur code...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
yeah it does not work. maybe it is only the implementation being wrong, I
want to hear the idea.
On Fri, Aug 6, 2010 at 2:55 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please
The thread is waiting for u anand :)..reply soon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@Algoboy , its pretty difficult to find the duplicate in constant space
unless u mention the range of numbers. Do the numbers lie between [1,n] ???
Unless some other information is given i don't think it is possible to come
out with a proper solution.
--
Thanks Regards,
Priyanka Chatterjee
travse array and check that if(a[i]==a[i+1]||a[i]==a[i+2]);
if more then n/2 no are there then that condition will satisfy ...adjust
with boundary condition
On Thu, Aug 5, 2010 at 6:36 AM, AlgoBoy manjunath.n...@gmail.com wrote:
an array in which n/2 elements are unique...and the remaning n/2
consider the test case of...
1 2 3 1...
1 repeated n/2 times and 2,3 are distinct n/2 elements
for this the algo will not work
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
If I understand the question correctly... there is an array of size n which
has n/2 distinct elements and one element is repeated n/2 times.
For e.g.:
n = 4: 1 2 3 3
n = 61 2 3 4 4 4
n = 81 2 3 4 5 5 5 5
So now this problem can be reduced to finding the first duplicate element
In constant space??? How? will you please elaborate?
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote:
If I understand the question correctly... there is an array of size n which
has n/2 distinct elements and one element is repeated n/2 times.
For e.g.:
n = 4: 1
compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last 4 elements...
repeated element can be found in 3 comparison for these 3 elements...
total no of comparison in worst case
(n/2+1)
Negi
On Thu, Aug 5, 2010 at 10:55 PM, Shiv ... shivsinha2...@gmail.com wrote:
In constant
Your test case is wrong. With this pattern you can have at max n/3
occurrences of 1. The questions says that repeated element has n/2
occurrences
On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
consider the test case of...
1 2 3 1...
1 repeated n/2 times and
Nice solution. Reduces number of comparisons to half of Ashish's algo. The
complexity remains O[n] though. Can it be made more efficient, like O[log n]
On Thu, Aug 5, 2010 at 10:59 PM, Pramod Negi negi.1...@gmail.com wrote:
compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last
http://codepad.org/8eDVyeBT
Using XOR logic we can find Duplicates in O(n)
On Thu, Aug 5, 2010 at 11:25 AM, ravindra patel ravindra.it...@gmail.comwrote:
Your test case is wrong. With this pattern you can have at max n/3
occurrences of 1. The questions says that repeated element has n/2
18 matches
Mail list logo
