 # Need help identifying exact different between two similar solutions for CHFING

For a problem on Codechef - https://www.codechef.com/problems/CHFING,
I submitted two programs that differs only on a part where a division occurs.

1st Solution https://www.codechef.com/viewsolution/24978403

``````import math
MOD = 1000000007
test = int(input())
for _ in range(test):
n,k = map(int, input().split())
first=k-1;
diff=n-1;
t = (first+diff)//(diff)
y=(2*(first)-(t-1)*(diff))
ans = (y*t)//2;
ans = ans%MOD
print(ans)
``````

2nd Solution https://www.codechef.com/viewsolution/24978385

``````import math
MOD = 1000000007
test = int(input())
for _ in range(test):
n,k = map(int, input().split())
first=k-1;
diff=n-1;
t = int((first+diff)/(diff))
y=(2*(first)-(t-1)*(diff))
ans = (y*t)//2;
ans = ans%MOD
print(ans)
``````

solution #1 passed all test cases but solution #2 fails for one test case.

The only difference is on line #8 where t is calculated as `t = (first+diff)//(diff)` in the 1st solution and `t = int((first+diff)/(diff))` in the 2nd solution.

Note that inputs are always integer, so variables `first` and `diff` are ints. And the code is in Python 3.6.

So does python returns different for x//y and int(x/y)? Or am I missing something else? Can someone kindly point me out why the second solution gives WA?

Edit: I came to know that these two are different for negative numbers. (https://stackoverflow.com/questions/56816677/does-x-y-and-intx-y-return-same-results-in-python). But input for this problem is non-negative and hence the variables first and diff also.

Edit #2: https://stackoverflow.com/a/56569910/7845063
the division operator behaves abnormally generally for numbers greater than 10 ^ 17.

``````x = 10000000000000000000006
if x / 2 == x // 2:
print("Hello")
else:
print("World")
``````

For the above code, World will be printed and not Hello. This is because 10000000000000000000006 / 2 will return 5e + 21, but 10000000000000000000006 // 2 will return the correct answer 5000000000000000000003. Even int(10000000000000000000006 / 2) will return 5000000000000000000000, which is incorrect.

floor divide gives lower value and int(x/y) gives round off value

and wont they be same in this case?

Tried to compare outputs from both approaches upto allowed limit. But answer is same for the iterations.

``````import math
MOD = 1000000007
#test = int(input())
#for _ in range(test):
for n in range(2,1000):
for k in range(1,1000):
#n,k = map(int, input().split())
first=k-1;
diff=n-1

t = (first+diff)//(diff)
y=(2*(first)-(t-1)*(diff))
ans = (y*t)//2;
ans = ans%MOD
#print(ans)

t2 = int((first+diff)/(diff))
y2=(2*(first)-(t2-1)*(diff))
ans2 = (y2*t2)//2;
ans2 = ans2%MOD
#print(ans2)

if ans == ans2:
continue
else:
print(n,k)``````

Yeah,
i checked it too!
Not exactly sure, but surely there must be a test case where the answer differs

Try this TC:
1
12 1000000000000000000

1 Like

wow, result differs for this TC. can you please explain why is this so?

Sorry, I don’t know the reason for this If you don’t get the answer here you can post it on stackoverflow.

Before posting here, i posted it SO, and it was marked as duplicate. Will edit that and will see if gets any answers. Thanks.

1 Like

from the SO link in edit2:
the division operator behaves abnormally generally for numbers greater than 10 ^ 17

Now i see the reason for the WA with the submission having ‘/’ operator. Cost me 80 points in june challenge. Thank you for your valuable input. May I ask how did you identify this exceptional case?

1 Like

I thought the reason for this abnormal behavior was that casting to int and using // operator take different number of significant digits for rounding off the number. So took a pair that generates a large number with recurring decimal representation as output. The assumption turned out to be wrong as in that case the numbers should only differ by 1. But a pair generating different output was achieved.
Was an interesting exception.

2 Likes

yeah i was saying this as well
there’s a difference in rounding off
floor division and typecasting has difference
i just couldn’t find exact solution
when i was doing this same problem i had a lot of WA because of it!