@Dave : sorry , i considered sorting a prerequisite for the given problem .
should have read it properly before posting.
On Tue, Dec 6, 2011 at 8:56 PM, Dave <dave_and_da...@juno.com> wrote:
> Atul: The original poster asked for an algorithm that is O(n) in time
> and O(1) space. So please tell us how you are going to sort the array
> with those limitations.
>
> Dave
>
> On Dec 6, 1:35 am, atul anand <atul.87fri...@gmail.com> wrote:
> > Given : 4 2 8 9 5 1 9
> >
> > sort the array.
> >
> > sorting: 1 2 4 5 8 9 9
> >
> > for ( i = 0 ; i < len ; i++)
> > {
> > if( i != len-1 )
> > {
> > if (arr[i]==arr[i+1])
> > {
> > printf("\nfound repeated element\n");
> > break;
> >
> > }
> > }
> >
> >
> >
> > }
> > On Mon, Nov 28, 2011 at 1:24 AM, Ankur Garg <ankurga...@gmail.com>
> wrote:
> > > Yup Gene ..rightly said and very well pointed out :) ..My Mistake :(
> >
> > > On Sun, Nov 27, 2011 at 12:49 AM, Gene <gene.ress...@gmail.com> wrote:
> >
> > >> 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.
> >
> > > --
> > > 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.
>
>
--
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.
