@ any solution less then nlogn would do + O(1) space
On Thu, Jul 8, 2010 at 12:38 AM, souravsain <souravs...@gmail.com> wrote:
> @jalaj
>
> Are we looking for a better than )(nlogn) time and O(1) space
> solution? What if our target?
>
> If a solution is required simple, then as mentioned by Satya, sort the
> numbers in O(nlogn) time and scan once in O(n) time. So we get the
> number repeated 3 times in O(nlogn) time and O(1) space.
>
> Sourav
>
> On Jul 7, 7:36 pm, Priyanka Chatterjee <dona.1...@gmail.com> wrote:
> > > 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
> > Indiahttp://priyanka-nit.blogspot.com/- 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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.
