>
>
> I am sceptical whether any XOR solution exits for your question. But if
> the question is modified as :
>
> *Only one number repeats once,* some no.s repeat twice and only one number
> repeat thrice, here is the XOR solution for that.
>
> suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
> in the example 1 repeats once and 5 repeats thrice.
>
> 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of times
> nullify) -O(N)
>
> ( let x=1, y=5
> As we know the no. repeating once and the no. repeating thrice are unequal,
> there must exist some bit 'k' such that x[k]!=y[k]. There may be more than
> such bits in x and y. But one such bit certainly yields T[k]=1 after x^y)
>
> 2> Now traverse along each bit of T( in binary) from left or right and
> consider T[i] =1 which is encountered first. store it . let b=i;
> (O(M) time and O(M) space to store binary if M is the bit length of T.)
>
> 3> T1= XOR(all elements in given array having bit b as 1)..... (O(N) time
> and O(M) space) ( time is O(MN) but as M<=32 , complexity remain O(N))
>
> 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time and
> O(M) space)
>
> One of (T1,T0) gives the no. that repeats once and the other gives the no
> that repeats thrice.
>
> 6> Now traverse the along array A and compute count for T1 and T0. The
> count that equals 3 gives the corresponding no. repeating thrice. -O(N)
>
> Time complexity is O(N+M) . Linear
> space complexity is O(M) to store binary form.
>
> But this algo certainly fails if more than one no. repeats once.
>
>
>
--
Thanks & Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science & Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
