Atul
a10 looks good however, when there are multiple such cases within the same string, it is is a problem because i would not know if the char is the real character of the string or part ofthe length eg a10115 is a valid string and can be interpreted as a011111 or a 10115 times. RLE is the first case not the second case which is pretty easy to take care. Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Fri, Mar 23, 2012 at 11:39 PM, atul anand <[email protected]>wrote: > @utkarsh: +1 > On 23 Mar 2012 18:38, "UTKARSH SRIVASTAV" <[email protected]> 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 <[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. >> > -- > 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.
