Hello friends ,

In the SQRDSUB problem from long challenge , I got wrong answer when I used long long int and got partial marks in the same code when I used unsigned long long int

Long long int , Wa , Absolute value :

https://www.codechef.com/viewsolution/31861811

Unsigned long long int , partial AC ( Absolute value not needed ) :

https://www.codechef.com/viewsolution/31655065

%4 , long long int , Wa , Absolute value :

https://www.codechef.com/viewsolution/31861832

%4 , unsigned long long int , partial AC ( Absolute value not needed ) :

https://www.codechef.com/viewsolution/31861896

Pls let me know why this is happening

Thanks

1 Like

it only matters because when you are taking input in an array , you areinserting a negative integer in an array and later changing it to its absolute value. unsigned will be required here because if we go in order you are taking â€śA negative integer first as inputâ€ť it doesnâ€™t matter if you later change a[i] to abs(a[i])

1 Like

@mshaheer2003 , thanks for pointing out

I have added new links and in all of them where absolute value is required i am doing but still getting wa

Pls let me know why

Thanks

```
for(ll i = 0; i < n; i++){
ll product = a[i];
if(a[i]%2 == 1 || a[i]%4 == 0 || a[i] == 0) count++;
for(ll j = i+1; j < n; j++){
product *= a[j];
if(product%2 == 1 || product%4 == 0 || product == 0) count++;
}
}
```

I believe the above should be the problem.

Remember, A[i] â‰¤ 10^9 and N â‰¤ 10^3 (for the first subtask)

The *product* of the whole array will be (10^9)^{(10^3)}, which, obviously, is beyond the limits of C++ (unsigned) long long int.

I took a small example, an array of length 5, and printed the product for each (i, j).

Somehow (for most of the testcases), the overflowed product retains the same modulo as the actual product.

So I created a random testcase generator.

This is a testcase for which your code outputs `124715`

, but the answer according to my code, another code, and your code with `unsigned long long`

is `124755`

.

Iâ€™m not sure what the issue is, but playing with overflow is a **bad** idea.

2 Likes

@crap_the_coder

Thatâ€™s because, overflow in `unsigned long long int`

is equivalent to mod 2^{64}, and heâ€™s only checking mod 4. Since 4 divides 2^{64}, it still works.

Even `signed long long int`

does mod 2^{64}, but anything above 2^{63}\ mod \ 2^{64}, becomes negative, so `product%2==1`

wonâ€™t hold. You also have to check `product%2==-1`

.

https://www.codechef.com/viewsolution/31864303

2 Likes

Ohhh, wow! Great observation! I forgot that in C++, `-1 % 2 = -1`

unlike Python

1 Like