Re: [algogeeks] Re: character count in array
@mohit: that will modify the original array and also time =O(nlogn)... On Mon, Sep 5, 2011 at 1:01 AM, Ankuj Gupta ankuj2...@gmail.com wrote: @mohit: that will modify the original array On Sep 4, 6:40 pm, sarath prasath prasathsar...@gmail.com wrote: here is my approach where i left the non repeating characters as it is and done some good code.. char * runlengthencode(char* str,int size) { int i,j,flag=0; for(i=0,j=1;str[i]str[j]jsize;i++,j++) { while(str[i]==str[j]) { j++; flag=1; } if(flag) { j=j-1; str[i+1]=48+(j-i+1); flag=0; i=j; j++; } } return str; } On Sat, Sep 3, 2011 at 6:54 PM, Aman Kumar amanas...@gmail.com wrote: Hiii if array is given like this arr[]=aabcabbcdeadef convert this array into like arr[]=a4b3c2d2e2f1 how can we do this can we do it with space complexity O(1). reply asap -- 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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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.
Re: [algogeeks] Re: character count in array
+1 rahul and +1 ankuj On Sat, Sep 3, 2011 at 11:37 AM, icy` vipe...@gmail.com wrote: 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.comwrote: 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 #includestdio.h #includeconio.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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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.
Re: [algogeeks] Re: character count in array
hey guys why hashing? can't we simply sort the array of characters in-place - space complexity O(1) . and then simply rearrange the array in-place with character+frequency. On Sun, Sep 4, 2011 at 3:13 PM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: +1 rahul and +1 ankuj On Sat, Sep 3, 2011 at 11:37 AM, icy` vipe...@gmail.com wrote: 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.comwrote: 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 #includestdio.h #includeconio.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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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. -- *MOHIT VERMA* -- 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.
Re: [algogeeks] Re: character count in array
@mohit :good one On Sun, Sep 4, 2011 at 4:34 PM, mohit verma mohit89m...@gmail.com wrote: hey guys why hashing? can't we simply sort the array of characters in-place - space complexity O(1) . and then simply rearrange the array in-place with character+frequency. On Sun, Sep 4, 2011 at 3:13 PM, bharatkumar bagana bagana.bharatku...@gmail.com wrote: +1 rahul and +1 ankuj On Sat, Sep 3, 2011 at 11:37 AM, icy` vipe...@gmail.com wrote: 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.comwrote: 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 #includestdio.h #includeconio.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. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- 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. -- *MOHIT VERMA* -- 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.
[algogeeks] Re: character count in array
@mohit: that will modify the original array On Sep 4, 6:40 pm, sarath prasath prasathsar...@gmail.com wrote: here is my approach where i left the non repeating characters as it is and done some good code.. char * runlengthencode(char* str,int size) { int i,j,flag=0; for(i=0,j=1;str[i]str[j]jsize;i++,j++) { while(str[i]==str[j]) { j++; flag=1; } if(flag) { j=j-1; str[i+1]=48+(j-i+1); flag=0; i=j; j++; } } return str; } On Sat, Sep 3, 2011 at 6:54 PM, Aman Kumar amanas...@gmail.com wrote: Hiii if array is given like this arr[]=aabcabbcdeadef convert this array into like arr[]=a4b3c2d2e2f1 how can we do this can we do it with space complexity O(1). reply asap -- 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.
[algogeeks] Re: character count in array
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 #includestdio.h #includeconio.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.
Re: [algogeeks] Re: character count in array
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 #includestdio.h #includeconio.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.
Re: [algogeeks] Re: character count in array
@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.comwrote: 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 #includestdio.h #includeconio.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.
[algogeeks] Re: character count in array
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.comwrote: 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 #includestdio.h #includeconio.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.
[algogeeks] Re: character count in array
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.comwrote: 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 #includestdio.h #includeconio.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.