what if we simply use the same char instead of '\0' that would reduce one traversal? (@utkarsh We discussed that earlier in lab.Did u found out the bug in this approach?) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Fri, Mar 23, 2012 at 6:38 PM, UTKARSH SRIVASTAV <usrivastav...@gmail.com>wrote: > 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 <atul.87fri...@gmail.com>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 <ashg...@gmail.com> 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 <atul.87fri...@gmail.com>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 >>>> <atul.87fri...@gmail.com>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 <gene.ress...@gmail.com> 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 <atul.87fri...@gmail.com> 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 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. >> > > > > -- > *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 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.