Consider the following snippet
int n;
cin>>n;
int n3=floor(n/3);
long long int sum=0;
sum+=(n3x(3+ n3x3))/2;
if n is of order 10^9 then why is the expression (n3(3+n3*3))/2 is overflowing
I want to know that what is the datatype of a expression how to decide it. i am using c++
(the same question gives me an ac if i change the datatype of n3 to long long int)
consider x as multiplication in sum+= expression
whenever you’re multiplying n3 * n3, it is overflowing as it’s declared as an int. Then the wrong value is stored in a long long int, so it will give you wrong ans. One way of avoiding overflow is if you multiply 1LL with n3. n3*1LL becomes long long int.
Okay, let me explain this with an example.
int a=3;
int b=2;
double c=a/b;
The value stored in c is NOT 1.5, its 1.0. Its explained as- c = (int)3/(int)2 = (int)(3/2) = (int)(1.5)=1 = 1.0 (since c is double).
Similarly, in sum+=(n3x(3+ n3x3))/2; after all the multiplication, overflow will occur. Then this overflowed result will get stored in sum. Declaring sum long long int means that sum can store upto K x 10^18, but if overflow occured before storing in sum, then its a problem.
`actually my main doubt is this only n3*n3 will have a type int according to u so how do you determined it. is the type of a "expression" same as of its variables?`
Quoting and answering-
only n3*n3 will have a type int
Yes. But point is, damage is already done. (int)10^9 x 10^9 =(int) 10^18 = -912232384 (some random garbage value after overflow).
so how do you determined it
This is basic knowledge of how your language works. Behind the scene knowledge comes handy many times.
is the type of a "expression" same as of its variables?
Yes. The expression is the type of “Highest” or “largest data type” encountered till now. Lets take this example-
int a=1000000; //a=10^6
long long int b=1;
long long int c=b+a*a;
How will this execute?
Firstly, remember the operator precedence. Although b (long long int) is written first in expression, the first thing computer evaluates is a x a (operator precedence).
So first it becomes a x a= 10^12 = -38438247 (random overflow value).
Then, c= b+ (-38438247) = -38438246 (type-long long int)
When we declare c as long long int while expression is int, then it means it wont overflow under conditions where overall indiviually expression remains int, but if summed over some range, it will cross int.
Eg-
for(i=0;i<100000;i++)
sum+= 1000*100;//Assuming sum is long long int - no overflow.
Here, the entire expression of 1000 x 100 = 10^5 remains within int range, however when summed up for all i, it becomes 10^10. But, no overflow will happen if we declare sum as long long int here.
In your case, the expression crosses the threshold of int, so you need to manually type case it to higher data type, or convert suitable variables to higher data type.
actually my main doubt is this only n3*n3 will have a type int according to u
so how do you determined it. is the type of a “expression” same as of its variables?
yes. see vijuu’s comment for better clarification. the expression is calculated at first and then it is stored.
Nice explanation @vijju123, except the overflowed result is not really “random”. Please don’t think of overflow as some mystical force working against programmers 
Overflow is a natural consequence of the way numbers are stored in memory and the result is always well-defined and predictable. Surprisingly, I can’t seem to find a comprehensive and simple article on the internet that explains overflow, but you’ll find various bits and pieces of information if you search for it 
Yes, I “instinctively” feel that overflow works like-
If limit is 10^9, while value stored is 10^9+50, then overflowed result is (-10^9 +50) [i.e. it will start from the bottom most limit by amount of overflow]. But i cannot back it up by any means so i didnt mention it. (In example i assumed that overflow is “large”, and since its hard to predict value then, random felt okish)
Please don't think of overflow as some mystical force working against programmers :P
That pretty much applied to older me! I got WA in one of my early cook-off Q, because I was doing same mistake as @divik544 . XD
thanks @vijju123 i was aware that it troubles me bcoz of overflow but just wanted to know when does a expression(not a data type a expression) overflow and that will depend on the type of expression so i asked this and your answer clears my doubts
Overflow is actually modding the value with 2^32-1
With the possibility of being negative, yes, i guess that as well.