Given two positive integers A and B, the task is to find the minimum number of increments/decrements required to be performed on either A or B to make both the numbers non-coprime.
Examples:
Input: A = 12, B = 3
Output: 0
Explanation:
As 12 & 3 are already non-coprimes, so the minimum count of increment/decrement operation required is 0.Input: A = 7, B = 17
Output: 2
Approach: The given problem can be solved based on the following observations:
- If A and B have Greatest Common Divisor greater than 1 then no increment or decrement is to be performed, as numbers are already non-coprime.
- Now, check for the difference of 1 in both directions for A as well as B. Hence it requires only a single step to convert any number to an even number.
- If none of the above two cases applies then 2 increments/decrements operations are required to make the numbers A and B to their nearest even number so that the numbers become non-co primes.
Based on the above observations, follow the steps below to solve the problem:
- If the GCD of A and B is not equal to 1, then print 0 as no operation is required.
- Else if the GCD of one of the pair {{A + 1, B}, {A – 1, B}, {A, B + 1}, {A, B – 1}} is not equal to 1, then print 1 as only one operations is required.
- Otherwise, print 2.
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(log(A, B))
Auxiliary Space: O(1)
Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.
