I am considering that I am having total size of buffer that is maximum of output or input buffer and input is given in the buffer.
My first approach of the solution was that 1. first traverse whole array and then count total number of characters that will be present in whole array. O(n) 2. fill the output array from rightmost side and start filling it until you reach 0th index. O(n) But it failed on this test case a1b1c4 here I could lost data b1 once I start filling character from right side.It faile because of characters whose count is 1. So I think just a change in algo will give me correct answer. 1. first traverse whole array and then count total number of characters that will be present in whole array and in case if the character count is 1 place '\0' in place of 1. O(n) 2. imagining \0 as space .convert this problem to removing white space from strings and compress it . Again can be done in O(n). 3. fill the output array from rightmost side and start filling it until you reach 0th index. O(n) Please correct me if I am wrong. On Thu, Mar 22, 2012 at 9:13 AM, atul anand <[email protected]> wrote: > @Ashish : a10 will be represented as aaaaaaaaaa . Here '1' and '0' are > character type in the given input , so you need to convert it into numeric > 10. > > > On Thu, Mar 22, 2012 at 1:09 AM, Ashish Goel <[email protected]> wrote: > >> Gene, Atul >> >> How would a string of say 257 or say 10 times a would be represented, >> will it be a10 or a<ascii of 10> >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> On Wed, Mar 21, 2012 at 2:04 PM, atul anand <[email protected]>wrote: >> >>> wasnt able to come up with an algo which would satisfy all the cases >>> input like a1b1c4 here output length is equal to input length . till now i >>> dont knw how to handle these type of input. :( :( >>> >>> On Wed, Mar 21, 2012 at 10:02 AM, atul anand <[email protected]>wrote: >>> >>>> @Gene : yes you are right , i misunderstood the problem . so m/m >>>> available is just enough to hold the output. >>>> thanks for correcting ... that would make this ques little interesting >>>> :) :)...i guess my first posted code can be modified to meet the >>>> requirement. >>>> i will post the updated code. >>>> >>>> On Tue, Mar 20, 2012 at 5:45 PM, Gene <[email protected]> wrote: >>>> >>>>> I don't think you're seeing the requirement completely. The problem >>>>> promises only that the output buffer will be big enough to hold the >>>>> output. You have made it huge. I tried your code on an input of >>>>> >>>>> a1b1c6 >>>>> >>>>> with the required output space of 8 characters (plus 1 for the C null >>>>> character), and it printed >>>>> >>>>> cccccc >>>>> >>>>> and stopped. >>>>> >>>>> Last night I realized there is another approach that will work in all >>>>> cases, so I deleted my post. I guess it wasn't deleted on the server >>>>> in your part of the world. >>>>> >>>>> You all can certainly work it out. You can't just copy the input to a >>>>> predetermined place in the buffer before processing it. It needs to be >>>>> placed carefully, and it needs to be processed from both ends to a >>>>> certain point in the middle. >>>>> >>>>> On Mar 20, 7:32 am, atul anand <[email protected]> wrote: >>>>> > using Gene logic , but we need to take care of number with more >>>>> than 1 >>>>> > digits , so updated gene's code is as follows :- >>>>> > >>>>> > #include<stdio.h> >>>>> > #define MAX 1000 >>>>> > >>>>> > int copy(char *str,int len) >>>>> > { >>>>> > int max_len=MAX-1,i; >>>>> > for(i=len-1;i>=0;i--) >>>>> > { >>>>> > str[max_len]=str[i]; >>>>> > max_len--; >>>>> > } >>>>> > return max_len+1; >>>>> > >>>>> > } >>>>> > >>>>> > void runLength(char *str) >>>>> > { >>>>> > unsigned int j,k=1,loop=0,res_len=0; >>>>> > int i,n_start; >>>>> > char c; >>>>> > /*copying input to the end of the buffer*/ >>>>> > n_start=copy(str,strlen(str)); >>>>> > >>>>> > for(i=MAX-1;i>=n_start;i--) >>>>> > { >>>>> > if(str[i]>='0' && str[i]<='9') >>>>> > { >>>>> > continue; >>>>> > } >>>>> > else >>>>> > { >>>>> > sscanf(&str[i],"%c%d",&c,&loop); >>>>> > for(j=0;j<loop;j++) >>>>> > { >>>>> > str[res_len]=c; >>>>> > res_len++; >>>>> > } >>>>> > } >>>>> > } >>>>> > str[res_len]='\0'; >>>>> > printf("\nDecoded Msg = %s\n",str); >>>>> > >>>>> > } >>>>> > >>>>> > int main() >>>>> > { >>>>> > char str[MAX]; >>>>> > memset(&str,0,MAX); >>>>> > printf("\nEnter String = "); >>>>> > scanf("%s",str); >>>>> > runLength(str); >>>>> > >>>>> > return 1; >>>>> > >>>>> > >>>>> > >>>>> > >>>>> > >>>>> > >>>>> > >>>>> > } >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
