CODEWITHSUNDEEP
coverflow
ComplicatedPhenomenon
ComplicatedPhenomenon

Reputation: 4199

runtime error: signed integer overflow: 99998 * 100000 cannot be represented in type 'int' [solution.c]

Trying to solve https://leetcode.com/problems/k-concatenation-maximum-sum/submissions/, I still got integer overflow when the data type is long

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int sum(int *nums, int numSize) {
    int ans = 0;
    for (int i = 0; i < numSize; ++i)
        ans += nums[i];
    return ans;
}

int KandaneAlgo(int *nums, int numSize) {
    int i, max_overall_so_far = 0, max_ending_here = 0;
    for (i = 0; i < numSize; ++i) {
        max_ending_here += nums[i];
        if (max_ending_here < 0)
            max_ending_here = 0;
        if (max_overall_so_far < max_ending_here)
            max_overall_so_far = max_ending_here;
    }
    return max_overall_so_far;
}

int kConcatenationMaxSum(int *arr, int arrSize, int k) {
    int mod = pow(10, 9) + 7;
    int ans;
    if (k > 1) {
        long tem = (k - 2) * max(sum(arr, arrSize), 0);
        int t1 = tem % mod;
        printf("%ld, %d, %d \n", tem, t1, mod);
        int arr2[2 * arrSize];
        for (int i = 0; i < 2 * arrSize; ++i)
            arr2[i] = arr[i - i / arrSize * arrSize];
        ans = (int)t1 +  KandaneAlgo(arr2, 2 * arrSize) % mod;
    } else {
        ans = KandaneAlgo(arr, arrSize) % mod;
    }
    return ans;
}

int main() {
    int arr[10] = { [0 ... 9] = 10000 };
    for (int i = 0; i < 10; ++i)
        printf("%d ", arr[i]);
    printf("\n");
    int tot = kConcatenationMaxSum(arr, 10, 100000);
    printf("%d \n", tot);
    return 0;
}

I locally debug with lldb and can see the output message of variable tem is wrong indeed, it should be 9999800000.

Upvotes: 2

Views: 1695

Answers (1)

salsaverde
salsaverde

Reputation: 81

This is because 9999800000 is larger than what can be stored in 32 bits. long only provides a minimum size guarantee of 32 bits. If you use long long for all the operands and result variable in the expression, it evaluates to the correct value. long long provides a minimum guarantee of 64 bits.
Check this for more details - https://en.wikipedia.org/wiki/C_data_types#Main_types

The following snippet worked for me:

long long tem = (long long)(k-2) * (long long)max(sum(arr, arrSize), 0);

Not sure about the rest of the algorithm, but this puts the correct value into tem.

Upvotes: 4

Related Questions