I was trying a question on codeforces problem
submitted to different code according to me they work same but one is accepted and another is showing WA on test case 23
accepted sol
wrong ans
can someone tell me where is the problem as both codes contain data type long long int
Constraint of n is 10^10^5 which is not in the range of long long data type. I am just thinking, how that solution got acceptedπ€
You got lucky. Submit again and again, you might get WA for the same code.
The reason is that, long long int can hold only up to 2^64
(approx 10^18
)
But the input in this problem can be up to 10^10^5
(which is huge)
How is it possible that by submitting the same code would result in WA because it has been accepted at first.
Expected solution is that you use string for n and then calculate the modulus using this method
How to compute mod of a big number? - GeeksforGeeks)%20(mod%20a)).
You donβt have to modulus the whole number or string just do it like this
string s;
cin>>s;
ll n=s.size();
ll x=(s[n-2]-β0β)*10+(s[n-1]-β0β);
if(x%4==0)
{
cout<<4<<endl;
}
else
cout<<0<<endl;
You just got lucky because of the weak test-cases for the problem and due to the undefined behavior of your program.
Your program will give the wrong answer to the following cases.
Test-Cases
1316548941819884919188919818918981932
Your Program Output
0
Correct Output
4
Generally, your program will give the wrong answer for all the cases in which the number is a multiple of 4 and the number of digits in n is greater than 18 as long long int
cannot store values greater than 9,223,372,036,854,775,807 i.e. 2^{63} - 1.
You already have figured out the logic, all you need is to write the program to handle large numbers.
Your program will give wrong answer if the number of digits in n is 1 because s[n - 2]
will give rise to out-of-bound error which in this case will get ignored hence generates some garbage value and hence gives the wrong answer.
You can modify the expression: x = (s[n - 2] - β0β) * 10 + (s[n - 1] - β0β)
to x = (s.at(n - 2) - β0β) * 10 + (s.at(n - 1) - β0β)
as at()
function does the bound checking first before returning the reference to the value at the location.
Documentation of at()
: http://www.cplusplus.com/reference/string/string/at/.
However, the actual logic to solve the problem in C++
:
static int compute_function(std :: string & n) {
int digit_count = n.size();
if(digit_count == 1) {
return !((n.at(0) - '0') % 4) ? 4 : 0;
}
return !((10 * (n.at(digit_count - 2) - '0') + (n.at(digit_count - 1) - '0')) % 4) ? 4 : 0;
}
Dude how did you post this snippet of the code