Help me in a question of codeforces

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πŸ€”

1 Like

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)

1 Like

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

https://www.geeksforgeeks.org/how-to-compute-mod-of-a-big-number/#:~:text=all%20possible%20solutions-,How%20to%20compute%20mod%20of%20a%20big%20number%3F,is%20expected%20as%20an%20integer.&text=The%20idea%20is%20to%20process,y)%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;
}

Try this out
Submission Link

Dude how did you post this snippet of the code

Refer: [Tutorial] CoLoR format the Code!

1 Like

Thanks for the advice @striker22 :heart: