Program to count minimum number of operations required to make numbers non coprime in Python?

Suppose we have two numbers A and B. Now in each operation, we can select any one of the number and increment it by 1 or decrement it by 1. We have to find the minimum number of operations we need such that the greatest common divisor between A and B is not 1.

So, if the input is like A = 8, B = 9, then the output will be 1, as we can select 9 then increase it to 10, so 8 and 10 are not coprime.

To solve this, we will follow these steps:

• if gcd of a and b is not same as 1, then

  • return 0

• if a is even or b is even, then

  • return 1

• otherwise,

  • if gcd of a + 1 and b is not same as 1 or gcd of a - 1 and b is not same as 1 or gcd of a and b - 1 is not same as 1 or gcd of a and b + 1 is not same as 1, then

    • return 1

  • otherwise,

    • return 2

Let us see the following implementation to get better understanding

Example

from math import gcd class Solution:    def solve(self, a, b):       if gcd(a, b) != 1:          return 0       if a % 2 == 0 or b % 2 == 0:          return 1       else:          if (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1 or gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1):             return 1       else:          return 2 ob = Solution() A = 8 B = 9 print(ob.solve(A, B))

Input

8,9

Output

1