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.
