Hello everyone,
Actually i am unable to understand a strange behavior of the code for the problem https://www.codechef.com/problems/COINS
if i submit this code, then it gives me WRONG ANSWER
#include<stdio.h>
#include<math.h>
int arr[500000]={0};
int t;
int func(int);
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",func(n));
}
}
int func(int a)
{
if(a<=500000)if(arr[a]!=0) return arr[a];
//if(a%12!=0) return a;
if((a/2)+(a/3)+(a/4) <=a) {/*if(a<=500000)arr[a]=a;*/return a;}
else {
t=func(a/2)+func(a/3)+func(a/4);
if(a<=500000) arr[a]=t;
return t;
}
}
But if i write printf("%u\n",func(n)); instead of printf("%d\n",func(n)); then it gives me Correct answer.
Whats the possible reason???
Thats because of overflow.
You are getting overflow for high values of n like 10^9 (the upper limit). Here is the test case-
Input
1000000000
Your Output (with %d)
-51749146
Your Output (with %u)
4243218150
%u is unsigned int speccifier, which has more range than typical int (I think it was 2x range of int, with condition that negative numbers cannot be stored in it). But data is lost from function. I will say, its pure luck, or weak test cases.
BTW, why did you put a condition-
if(a<=500000)if(arr[a]!=0) return arr[a];
when the length of array itself is 500000?? Did it not give you SIGSEV or undefined behaviour when you tried to access arr[500000]??
Thanks for the reply. I already know what you have told, but the function is returning int in both cases, so if there is a overflow, it must loose its data there only.
Yes, it will lose data there. You can say that in your case, 2 (actually 3) minuses made a plus. I think one of the more experienced member can better comment on this.
@tanujyadav97 In your function you didn’t lost your data, it’s just that answer overflowed and went to -ve side. So when you did %u it all become same because fortunately answer was in the unsigned range otherwise the problem would have still existed.
1 Like
Thats possible. If the overflow is not large,what @agrocks23 says makes perfect sense.
Yes, this could be the right answer if the number exceeds the range of data type it goes on a cycle printing negative numbers but @vijju123 why did you say if the overflow is not large (I guess you mean that if the overflow is not exceeding the unsigned int range). A long long will also do this , right?
%u treats the integer as unsigned, whereas %d treats the integer as signed. If the integer is between 0 an INT_MAX (which is 231-1 on 32-bit systems), then the output is identical for both cases.
It only makes a difference if the integer is negative (for signed inputs) or between INT_MAX+1 and UINT_MAX (e.g. between 231 and 232-1). In that case, if you use the %d specifier, you’ll get a negative number, whereas if you use %u, you’ll get a large positive number.
I got this explanation from stackoverflow https://stackoverflow.com/questions/5208641/difference-between-printing-a-memory-address-using-u-and-d-in-c
I meant the overflow isnt that large. Lets say, if answer was 10^15, then its a large overflow and then even unsigned into wont fix it. In this case, overflow was small, such that after adding the correction, it fits in the range.
@agrocks23 thanks, i think you are correct
@vijju123 actually, its not my code, my friend asked this to me
You wrote 231 and 232 instead of 2^31 and 2^32.