Just use a hash to count frequency of something; e.g. in ruby:
ar= %w(a a b c a b b c d e a d e f)
freq=Hash.new(0)
ar.each {|c| freq[c]+=1}
p freq
#output
#{"a"=>4, "b"=>3, "c"=>2, "d"=>2, "e"=>2, "f"=>1}
you could only do it in place in O(1) only if your input array is
already 2*(number of all possible characters) size, but you didnt
mention size of input array. For example, what if input was just
[a,b,c,d,e] ? The size is 5. You cant just convert the input
into [a,1,b,1,c,1,d,1,e,1] without increasing the size to 10. So
hash is the better method.
On Sep 3, 11:04 am, Ankuj Gupta <ankuj2...@gmail.com> wrote:
> if for all inputs you array remains of same size we can take it as
> constant space
>
> On Sep 3, 7:49 pm, rajul jain <rajuljain...@gmail.com> wrote:
>
>
>
>
>
>
>
> > @ankuj just want to clarify that in hashing method we require array of
> > fixed size let say arr[26] , so is it considered as constant space or not?
>
> > On Sat, Sep 3, 2011 at 8:02 PM, siddharam suresh
> > <siddharam....@gmail.com>wrote:
>
> > > sol already posted please search old thread
> > > Thank you,
> > > Sid.
>
> > > On Sat, Sep 3, 2011 at 8:01 PM, Ankuj Gupta <ankuj2...@gmail.com> wrote:
>
> > >> If we take our input to be characters a-z ans A-Z then we require
> > >> fixed space which can be treated as O(1).
> > >> On Sep 3, 7:10 pm, teja bala <pawanjalsa.t...@gmail.com> wrote:
> > >> > this 'll work if u i/p the string in dis manner
> > >> > aaabbcc(consecutive same)
> > >> > a3b2c2
>
> > >> > #include<stdio.h>
> > >> > #include<conio.h>
> > >> > main()
> > >> > {
> > >> > int x=1,i=0;
> > >> > char a[100];
> > >> > gets(a);
> > >> > while(a[i]!='\0')
> > >> > {
> > >> > while(a[i]==a[i+1])
> > >> > {
> > >> > x++;
> > >> > i++;
> > >> > }
> > >> > printf("%c%d",a[i],x);
> > >> > x=1;
> > >> > i++;
> > >> > }
> > >> > getchar();
>
> > >> > }
>
> > >> --
> > >> 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.
