Isn't this overkill? If you're already using a set, just check the set
before you insert each new element, and you'll discover the
duplicates:
S = empty
while i = input item existss
if i in S output "i has a duplicate";
insert i in S
end
XOR is generally useful only for detecting a single item that's
included in a list an odd number of times rather than an even number
of times.
On Nov 24, 3:56 pm, Ankur Garg <ankurga...@gmail.com> wrote:
> ^^+1..how matrix formed ??
> But as Gene said we can use a set to store all the unique elements
>
> Now we xor all the set elements and then xor them with the elements of the
> array . This wud give us the repeating element as all the elements coming
> once will be 0(xored twice) and repeating element wud be xored twice .
>
> To code it as follows
>
> int FindSingle(int a[],int n){
> set<int>s;
> s.insert(a,a+n);
> set<int>::iterator it;
> it = s.begin();
> int XOR= *it;
> it++;
> while(it!=s.end()){
> XOR =XOR^*it;
> it++;}
>
> for(int i=0;i<n;i++)
> XOR=XOR^a[i];
> return XOR;
>
> }
>
> On Fri, Nov 25, 2011 at 1:03 AM, kumar raja <rajkumar.cs...@gmail.com>wrote:
>
>
>
> > @Anup:
> > Atleast u tell me how the M has formed???
>
> > On 24 November 2011 11:21, Anup Ghatage <ghat...@gmail.com> wrote:
>
> >> @kunzmilan
> >> Nice idea, how do you decide the row-size or column-size of the matrix?
>
> >> On Thu, Nov 24, 2011 at 8:00 PM, kumar raja
> >> <rajkumar.cs...@gmail.com>wrote:
>
> >>> @kunzmilan :
> >>> Can u please maintain the clarity ??
> >>> How did u find the M
>
> >>> if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it...
>
> >>> On 24 November 2011 06:15, kunzmize an <kunzmi...@atlas.cz> wrote:
>
> >>>> On 24 lis, 09:09, kumar raja <rajkumar.cs...@gmail.com> wrote:
> >>>> > @kunzmilan : i did not get u, once explain with example...
>
> >>>> > On 23 November 2011 23:47, kunzmilan <kunzmi...@atlas.cz> wrote:
> >>>> Matrix M
> >>>> 0 1 0
> >>>> 0 1 0
> >>>> 1 0 0
> >>>> multiplied with M(T)
> >>>> 0 0 1
> >>>> 1 1 0
> >>>> 0 0 0
> >>>> gives
> >>>> 1 0 0
> >>>> 0 2 0
> >>>> 0 0 0.
> >>>> On its diagonal are numbers of repeated elements.
> >>>> kunzmilan
>
> >>>> > > On 24 lis, 07:02, kumar raja <rajkumar.cs...@gmail.com> wrote:
> >>>> > > > In the given array all the elements occur single time except one
> >>>> element
> >>>> > > > which occurs 2 times find it in O(n) time and O(1) space.
>
> >>>> > > > e.g. 2 3 4 9 3 7
>
> >>>> > > > output :3
>
> >>>> > > > If such a solution exist can we extend the logic to find "All the
> >>>> > > repeated
> >>>> > > > elements in an array in O(n) time and O(1) space"
>
> >>>> > > > --
> >>>> > > > Regards
> >>>> > > > Kumar Raja
> >>>> > > > M.Tech(SIT)
> >>>> > > > IIT Kharagpur,
> >>>> > > > 10it60...@iitkgp.ac.in
> >>>> > > > Write the list in the form of a matrix M, e.g.
> >>>> > > > 0 1 0 0...
> >>>> > > > 0 0 1 0...
> >>>> > > > 0 0 0 1...
> >>>> > > > ......etc.,
> >>>> > > > and its quadratic form M(T)M shows, how many times each element
> >>>> repeats.
> >>>> > > kunzmilan
>
> >>>> > > --
> >>>> > > 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, send email to
> >>>> > > algogeeks+unsubscr...@googlegroups.com.
> >>>> > > For more options, visit this group at
> >>>> > >http://groups.google.com/group/algogeeks?hl=en.
>
> >>>> > --
> >>>> > Regards
> >>>> > Kumar Raja
> >>>> > M.Tech(SIT)
> >>>> > IIT Kharagpur,
> >>>> > 10it60...@iitkgp.ac.in
>
> >>>> --
> >>>> 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, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com.
> >>>> For more options, visit this group at
> >>>>http://groups.google.com/group/algogeeks?hl=en.
>
> >>> --
> >>> Regards
> >>> Kumar Raja
> >>> M.Tech(SIT)
> >>> IIT Kharagpur,
> >>> 10it60...@iitkgp.ac.in
>
> >>> --
> >>> 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, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> Anup Ghatage
>
> >> --
> >> 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, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > 10it60...@iitkgp.ac.in
>
> > --
> > 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, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
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, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
