Given two integers A and B and a range defined by two integers C and D, the task is to convert A to B using the minimum number of operations possible. The only allowed operations are to add or subtract any integer greater than or equal to E to A. However, after each operation, the resulting value of A must lie in the range C to D (inclusive). If it is not possible to obtain B from A using these operations, return -1.
Examples:
Input: A = 4, B = 5, C = 0, D = 15, E = 5
Output: 2
Explanation: In first operation add 6 to A. A becomes 10. In second operation, subtract 5 from A. Now A becomes 5, which is equal to B. Note that after both operations, A lies in the range [C, D]. Also, the numbers added or subtracted (6 and 5) are greater than or equal to E.Input: A = 3, B = 4, C = 3, D = 5, E = 6
Output: -1
Approach: To solve the problem follow the below idea:
- If A = B, in this case, 0 operations are required to convert A to B.
- If the absolute difference between A and B is greater than or equal to E, 1 operation is sufficient to make A equal to B. The integer value E = |B-A| can be added or subtracted to/from A to make it equal to B.
- There exists an integer X between C and D, such that |A-X| ≥ E and |B-X| ≥ E, in this case, A can be made B in 2 operations: A -> C -> B or A -> D -> B.
- If we cannot make A equal to B through one of the boundaries as in 3rd case, we will require 3 operations to do so, i.e. we will go through both the boundaries C and D:
A -> C -> D -> B or A -> D -> C -> B.- If any of the above conditions are not satisfied, then it is not possible to convert A to B. Hence, we will return -1.
Below are the steps for the above approach:
- If A is equal to B, return 0.
- If the absolute difference between A and B is greater than or equal to E, return 1.
- If the difference between D and the greater of A and B is greater than or equal to E, or if the difference between the lesser of A and B and C is greater than or equal to E, return 2.
- Check if (D-B ≥ E && A-C ≥ E) or (D-A ≥ E && B-C ≥ E) is true, and return 3.
- Else returns -1.
Below is the code for the above approach:
C++
|
Time Complexity: O(1)
Auxiliary space: O(1)