This code runs on my IDE but not Leetcode which returns "heap-buffer-overflow"

Question

The Leetcode question is "Integer to Roman". Here is my solution:

char* intToRoman(int num) {
    char numerals[] = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
    int numeral_vals[] = { 1000, 500, 100, 50, 10, 5, 1 };
    int prefix_minus[] = { 100, 100, 10, 10, 1, 1, 0 };
    int arr_len = 7;
    char* roman = (char*)malloc(sizeof(char) * 100);
    int romanLen = 0;

    for (int i = 0; i < arr_len; i++) {
        while (num >= numeral_vals[i]) {
            roman[romanLen] = numerals[i];
            romanLen++;
            num -= numeral_vals[i];
        }

        int prefixed_val = numeral_vals[i] - prefix_minus[i];
        if (num >= prefixed_val) {
            roman[romanLen] = prefixed_val;
            romanLen++;
            num -= prefixed_val;
        }
    }

    return roman;
}

With input of 3 through VS Code, it works. But on Leetcode itself, it gives me a:

=================================================================
==34==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60b000000154 at pc 0x562764199bbb bp 0x7ffe8128ec40 sp 0x7ffe8128ec30
READ of size 1 at 0x60b000000154 thread T0
    #2 0x7f53a881f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x60b000000154 is located 0 bytes to the right of 100-byte region [0x60b0000000f0,0x60b000000154)
allocated by thread T0 here:
    #0 0x7f53a9464bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7f53a881f0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c167fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c167fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c167fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c167fff8000: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x0c167fff8010: fd fd fd fd fd fa fa fa fa fa fa fa fa fa 00 00
=>0x0c167fff8020: 00 00 00 00 00 00 00 00 00 00[04]fa fa fa fa fa
  0x0c167fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c167fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c167fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c167fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c167fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==34==ABORTING

After some checking, it seems like mallocing is fine, but I can't return "roman". But what's wrong with that? VS Code handles it just fine.

Also, there's not a tag for leetcode, what can I use instead?

Is this function expected to return a string? Because it does not provide a string terminator. — John Bollinger
– John Bollinger, Commented Oct 21, 2022 at 2:06
Using calloc instead of malloc will initialize all of the values to 0 which fixes the termination issue. Still needs some work for a value of 1234 though. godbolt.org/z/cErYE56M7 Happy Debugging! You should add -Wall -Wextra -pedantic -fsanitize=address,undefined to your compile flags in VS Code to help you find issues like this. Pay attention to any warnings you see. — Retired Ninja
– Retired Ninja, Commented Oct 21, 2022 at 2:20
Please add a minimal reproducible example which shows the call of your function. — the busybee
– the busybee, Commented Oct 21, 2022 at 8:30

user20276305 · Accepted Answer · 2022-10-21 13:56:42Z

In the line

roman[romanLen] = prefixed_val;

roman[romanLen], which is a part of the output string, is assigned prefixed_val, which is an auxiliary variable. I don't know this algorithm, but this seems incorrect. Indeed, for the number 4 the function returns a char array holding 4 followed by 99 zeros. The test (I replaced malloc with calloc in the function to be sure to safely print the whole string):

char *result = intToRoman(4);
for (int k = 0; k < 100; ++k) {
  printf("%d,", result[k]);
}

There are also other problems, as pointed out by John Bollinger, dimich and Retired Ninja in the comments to the question. Remember that malloc does not initialize the memory (see man 3 malloc), but calloc does. So, the string roman should be explicitly terminated with '\0' before doing any operations in which you assume it is a string.

I don't know about the error produced by Leetcode, but maybe this information will help you anyway.

By the way, in the future, you may consider using Valgrind. It produces quite helpful messages when it comes to handling memory. If you use gcc, remember to use it with the flag -g. This flag makes Valgrind to add line numbers to its output.

Collectives™ on Stack Overflow

This code runs on my IDE but not Leetcode which returns "heap-buffer-overflow"

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