Pagadala Vikramaditya Pagadala Vikramaditya - 16 days ago 8
C++ Question

casting int to unsigned long long

I was solving a problem wherein the task was to output the result of a pascal triangle at a given row mentioned by a user.

https://leetcode.com/problems/pascals-triangle-ii/

I wrote my solution which had issues storing huge factorial results.

vector<int> getRow(int rowIndex) {

vector<int> v;

int C = 1;
v.push_back(1);

for (int i = 1; i <= rowIndex; i++)
{
printf("%d ", C);
C = C * (rowIndex +1 - i) / i;
v.push_back(C);
}

return v;
}


On going through these questions,

What range of values can integer types store in C++

How many bytes is unsigned long long?

and going through some other sources, i made the following change which gave me the required result.

C = (unsigned long long)C * (rowIndex +1 - i) / i;


Since "C" is of type int and my vector v stores int, i wanted to know why would a cast unsigned long long still give me valid results.

Answer

The sub-expression C * (rowIndex +1 - i) can overflow before your division. By casting C to a larger data-type then the whole expression becomes that type, so the multiplication will not overflow. Then after the division with i the result is converted to an int again, but because of the division it is within range of an int.

Note that this is only for the values you currently have. If you continue with even higher values then sooner or later you will have overflows that can't be fixed by such a cast.