Given integers X, Y, and Ok, the duty is to make X and Y equal in no more than Ok operations by making use of the next operations:
- Select an integer A and make X = X/A, (the place A is an integer that’s higher than 1 and never equal to X).
- Select an integer A and make Y = Y/A, (the place A is an integer that’s higher than 1 and never equal to Y).
Examples:
Enter: X = 10, Y = 20, Ok = 4
Output: YES
Rationalization: One optimum answer to make them equal is:
First select A = 2 and do X = X/2 so now X is the same as 5.
Now select A = 4 and do Y = Y/4 so now Y is the same as 5.
Since we’ve got utilized solely two operations right here which is lower than OkÂ
to make X and Y equal and in addition higher than one.
Due to this fact the reply is YES.Enter: X = 2, Y = 27, Ok = 1
Output: NO
Rationalization: There isn’t any attainable approach to make X and Y equalÂ
in lower than or equal to 1 Operation.
Â
Method: To resolve the issue observe the beneath thought:
Listed below are solely two instances attainable:
- When Ok is the same as one andÂ
- When Ok is larger than 1
If Ok is the same as one then it’s attainable to make X and Y equal solely when both X is divisible by Y or Y is divisible by X
If Ok is larger than 1 then X and Y could be equal and higher than 1 solely when their GCD is larger than 1.
Observe the steps talked about beneath to implement the thought:
- Verify if Ok = 1:
- In that case, discover out if any of them is a divisor of the opposite.
- In any other case, discover the GCD of the numbers.
- If the GCD is 1 then it’s not attainable.
- In any other case, a solution all the time exists.
Under is the implementation for the above strategy:
C++
|
Time Complexity: O(1)
Auxiliary House: O(1)