My code triggers a defect of OJ


  • 0
    T

    My solution is not good enough, but it triggers a defect of OJ. After submission it shows:

     Submission Result: Wrong AnswerMore Details 
    
     Input:	"0", "0"
     Output:	"0"
     Expected:	"0"
    

    In my solution I first fill enough '\0' into the result string, then update the string with digit, finally restore the digits to characters.

    Here output is expected but result is wrong. When I add a line to resize the result string, the solution is accepted. Curious about how OJ compares output string with expected result, does it compare both size and content?

    Below is my code:

    class Solution {
    public:
        string multiply(string num1, string num2) {
            int len1 = num1.size();        
            int len2 = num2.size();        
            if(len1 == 0 || len2 == 0) 
                return "0";
            string res(len1+len2, 0);
    
            int i, j, k, carry;
            int digit_count = 0;
            for(i = len2-1; i>=0; i--) {
                for(j = len1-1; j>=0; j--) {
                    int cur = len2-1-i+len1-1-j; 
                    res[cur] = res[cur] + (num1[j]-'0') * (num2[i]-'0');
                    // fixed after second submission
                    if(res[cur] == 0) continue;
    
                    digit_count = max(digit_count, cur);
                    carry=0;
                    k = cur;
                    do {
                        int sum = res[k] + carry;
                        res[k] = sum%10;
                        carry = sum/10;
                    } while(carry&&++k <= digit_count); 
    
                    if(k>digit_count && carry) 
                        res[++digit_count] = carry;
                }
            }
    
            // if we didn't comment out this line, letcode OJ will be silly!!
            // res.resize(digit_count+1);
    
            // reserve string and restore numbers to characters
            for(i = 0, j = digit_count; i <= j; i++, j--) 
                swap(res[i], res[j]);
            for(i = 0; i <= digit_count; i++) 
                res[i] = res[i]+'0';
            
            return res;
        }
    };

  • 0
    C

    This is not a problem of LeetCode. It is using std::string comparison. Unlike C, C++ "string"s are not null terminated though the
    implementation differs according to platform, the representation is generally like { size, data* }. Hence, comparison consists of comparing both
    content and the size.


    You can find one implementaion (used in GNU gcc) of the string comparion in libstdc++ @line 2210 here.
    The compare function does the following

    1. compare the contents of string upto shorter string ie. std::min(l1, l2)
    2. if equal compare sizes (l1 > l2 ? ) => return value from length compare
    3. otherwise => return value from content compare

    What may be puzzling is the LeetCode error message which shows the your output and the expected values as same. I presume that extra
    null char is removed while formating the text to html since it's non-printable.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.