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 zer
@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
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
algogeeks+unsubscr...@googlegroup
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
wrote:
> 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...
>
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 algoge...@googlegroup
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
algogeeks+u
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
wrote:
> no the array is unsorted..
>
> On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal wrote:
>
>> If I understand the question correctly...
no the array is unsorted..
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal 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 4 4
>n =
Using median, you can do it!
Thanks,
Sathaiah
On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy 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/...
>
> --
> You received
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 wrote:
> http://codepad.org/8eDVyeBT
>
> Using XOR logic we can find Duplicates in O(n)
>
>
> On Thu, Aug 5, 2010 at 11:25 AM,
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 wrote:
> 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,
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 wrote:
> compare pair wise i.e a[0] and a[1]a[2] and a[3]..
>
> leave out last 4 elements...
>
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
wrote:
> consider the test case of...
>
> 1 2 3 1...
>
> 1 repeated n/2 times and 2,3 are distinct n/
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 ... wrote:
> In constant space??? How? will you p
In constant space??? How? will you please elaborate?
On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal 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 =
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
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.
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 wrote:
> an array in which n/2 elements are unique...and the remaning n/2 have
> the same elements
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/...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this grou
19 matches
Mail list logo