Min operations to convert A to B by incrementing A in the given range
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++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to find minimum operations // to covert A to B int minOperations( int A, int B, int C, int D, int E) { // Case-1 if (A == B) { return 0; } // Case-2 else if ( abs (A - B) >= E) { return 1; } // Case-3 else if (D - max(A, B) >= E || min(A, B) - C >= E) { return 2; } // Case-4 else if ((D - B >= E && A - C >= E) || (D - A >= E && B - C >= E)) { return 3; } // Case-5 else { return -1; } } // Driver code int32_t main() { int A = 4, B = 5, C = 0, D = 15, E = 5; int answer = minOperations(A, B, C, D, E); // Function Call cout << answer << endl; return 0; } |
Java
import java.util.*; class Main { // Function to find minimum operations // to covert A to B public static long minOperations( long A, long B, long C, long D, long E) { // Case-1 if (A == B) { return 0 ; } // Case-2 else if (Math.abs(A - B) >= E) { return 1 ; } // Case-3 else if (D - Math.max(A, B) >= E || Math.min(A, B) - C >= E) { return 2 ; } // Case-4 else if ((D - B >= E && A - C >= E) || (D - A >= E && B - C >= E)) { return 3 ; } // Case-5 else { return - 1 ; } } // Driver code public static void main(String[] args) { long A = 4 , B = 5 , C = 0 , D = 15 , E = 5 ; long answer = minOperations(A, B, C, D, E); // Function Call System.out.println(answer); } } |
Python3
# Python code for the above approach import sys def minOperations(A, B, C, D, E): # Case-1 if A = = B: return 0 # Case-2 elif abs (A - B) > = E: return 1 # Case-3 elif D - max (A, B) > = E or min (A, B) - C > = E: return 2 # Case-4 elif (D - B > = E and A - C > = E) or (D - A > = E and B - C > = E): return 3 # Case-5 else : return - 1 # Driver code if __name__ = = '__main__' : A = 4 B = 5 C = 0 D = 15 E = 5 # Function call answer = minOperations(A, B, C, D, E) print (answer) |
C#
// C# code for the above approach using System; class GFG { // Function to find minimum operations // to covert A to B static int MinOperations( int A, int B, int C, int D, int E) { // Case-1 if (A == B) { return 0; } // Case-2 else if (Math.Abs(A - B) >= E) { return 1; } // Case-3 else if (D - Math.Max(A, B) >= E || Math.Min(A, B) - C >= E) { return 2; } // Case-4 else if ((D - B >= E && A - C >= E) || (D - A >= E && B - C >= E)) { return 3; } // Case-5 else { return -1; } } // Driver's code static void Main( string [] args) { // Input int A = 4, B = 5, C = 0, D = 15, E = 5; int answer = MinOperations(A, B, C, D, E); // Function Call Console.WriteLine(answer); } } |
Javascript
// Javascript code for the above approach function minOperations(A, B, C, D, E) { // Case-1: if A and B are already equal, then no operations are required if (A == B) { return 0; } // Case-2: if the absolute difference between A and B // is greater than or equal to E, then only one operation is required else if (Math.abs(A - B) >= E) { return 1; } // Case-3: if either A or B can be made equal to C or D by // just one operation, then only two operations are required else if (D - Math.max(A, B) >= E || Math.min(A, B) - C >= E) { return 2; } // Case-4: if it is possible to make A and B both equal to C or D or // any value in between C and D by two operations, then only three // operations are required else if ((D - B >= E && A - C >= E) || (D - A >= E && B - C >= E)) { return 3; } // Case-5: if none of the above cases are applicable, // then it is impossible to make A and B equal by performing // any number of operations else { return -1; } } // Driver code let A = 4, B = 5, C = 0, D = 15, E = 5; let answer = minOperations(A, B, C, D, E); // Function Call console.log(answer); //This Code is Contributed By Vikas Bishnoi (vikas20noi) |
2
Time Complexity: O(1)
Auxiliary space: O(1)