A c solution for leetcode 38 count and say confuse me

Question

here is the problem count and say my accept code below here. I wrote the main function,when submit just copy the countAndSay function.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

char* countAndSay(int n) 
{
    if( n == 1 ) 
        return "1";
    char *cur = (char *)malloc(2*sizeof(char));
    char *res;
    cur[0]='1';
    cur[1]='\0';

    int len, idx, j, count;
    for(int i = 2; i <= n; ++i)
    {
       len = strlen(cur);
       res = (char *)malloc(len * 2 + 1);
       memset(res, '\0', len * 2 + 1);
       count = 1;
       for(idx = 1, j = 0; idx < len; ++idx)
       {
          if(cur[idx] == cur[idx-1])
          {
             ++count;
          }
          else
          {
             res[j++] = '0' + count;
             res[j++] = cur[idx-1];
             count = 1;
          }
       }//end of for

       res[j++] = '0' + count;
       res[j++] = cur[len-1];
       free(cur);
       cur = res;
    }   
    return cur;
}

int main()
{
   char *s = countAndSay(INT_MAX);
   printf("%s\n",s);
   free(s); 
   return 0;
}

This code i saw from the discuss part and modfiy part of it.I just confused why use res[j++] = '0' + count since count may be 11 or 12,when count bigger than 9,res[j++] is not a char between '0' and '9',so i ran the code,and it went wrong.

ctci(1720,0x100392380) malloc: * mach_vm_map(size=18446744071713468416) failed (error code=3) * error: can't allocate region *** set a breakpoint in malloc_error_break to debug Program ended with exit code: 9

i guess may be the series is too long,my computer's memory not enough.So i change the num to 500,still got wrong.

Just can not figuer out why.

following the advice of @WhozCraig,i print the len to malloc,here is the result.

1
2
2
4
6
6
8
10
14
20
26
34
46
62
78
102
134
176
226
302
408
528
678
904
1182
1540
2012
2606
3410
4462
5808
7586
9898
12884
16774
21890
28528
37158
48410
63138
82350
107312
139984
182376
237746
310036
403966
526646
686646
894810
1166642
1520986
1982710
2584304
3369156
4391702
5724486
7462860
9727930
12680852
16530884
21549544
28091184
36619162
47736936
62226614
81117366
105745224
137842560
179691598
234241786
305351794
398049970
518891358
676414798
881752750
1149440192
ctci(1828,0x100392380) malloc: *** mach_vm_map(size=18446744071713468416) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Program ended with exit code: 9

so 1149440192B ,1149440192/(1024*1024)MB=1096MB,i just watch the memory left,it is bigger than 1096.1915893555MB.

I think you would do well to put a printf("i=%d, len=%d\n", i, len); at the top of your loop, immediately after the (unnecessary) strlen invoke. You'd be surprised how much memory this used, and how fast it uses it. Something tells me your algorithm has... issues. — WhozCraig
– WhozCraig, Commented Apr 25, 2018 at 16:26
@WhozCraig thanks for your advice,i will see this tomorrow,it's late ,must to sleep now. thanks again. — 52coder
– 52coder, Commented Apr 25, 2018 at 16:34
Don't cast the value returned from malloc(). If you have the correct prototype in scope the cast is useless; if you do not have the correct prototype in scope, the cast is likely to silence any helpful warning the compiler might otherwise have provided. — mlp
– mlp, Commented Apr 25, 2018 at 18:02

Joshua · Accepted Answer · 2019-03-10 19:54:47Z

0

You ran out of memory.

Every pass around the loop for(int i = 2; i <= n; ++i) potentially doubles the size of res, and you called it with n == INT_MAX. Ain't no computer in the universe that can allocate 1<<INT_MAX bytes of RAM.

The problem statement says to run for n == 30. Your output suggests enough RAM to run for 30.

answered Mar 10, 2019 at 19:54

Joshua

43.6k9 gold badges80 silver badges153 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

A c solution for leetcode 38 count and say confuse me

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related