CODEWITHSUNDEEP
c++casting
cryptomanic
cryptomanic

Reputation: 6316

What is the advantage of typecasting int to long long during calculations?

I was getting wrong answer by the below function. 

vector<int> repeatedNumber(const vector<int> &A) {
    int n = A.size();
    long long linear_sum = 0,square_sum = 0;
    int i = 0;
    for(;i<n;i++){
        linear_sum += A[i];          //LINE 1
        square_sum += A[i]*A[i];     //LINE 2
    }
    linear_sum = linear_sum - (n*(n+1))/2;
    square_sum = square_sum - (n*(n+1)*(2*n+1))/6;
    square_sum /= linear_sum;
    vector<int> ans;
    ans.push_back((linear_sum+square_sum)/2);
    ans.push_back((-linear_sum+square_sum)/2);
    return ans;
}

But when I replaced LINE 1 and LINE 2 with :

linear_sum += (long long)A[i];          
square_sum += (long long)A[i]*(long long)A[i];

I got the correct answer.Why just typecasting the int to long long solves the problem.

Upvotes: 4

Views: 134

Answers (2)

6502
6502

Reputation: 114579

When you multiply two int values the result is computed as an int.

If the values when multiplied are too big for an int you get "undefined behavior" (in most common hardware you just get a seemingly random result).

For example 33554432 (i.e. 1<<25 == 225) is ok for a 32-bit integer, but its square 1125899906842624 (i.e. 250) is not.

Casting to long long the terms before computing the multiplication you're hopefully expanding the range in which the computations are done correctly.

These problems are not present in languages that natively provide arbitrary precision integers like Python or Lisp.

Note it's possible that int and long long are indeed the same size (you can only be sure that a long long is not smaller than an int).

Upvotes: 3

qPCR4vir
qPCR4vir

Reputation: 3571

The key is here:

A[i]*A[i]

This can be too big, overflow the int, and only after that, is converted to long long, but.

(long long)A[i]*(long long)A[i];

is first converted and then multiply and may not overflow the long long

Upvotes: 2

Related Questions