Given two positive integers A and B. The task is to find the minimum number of operations required to convert number A into B. In a move, any one of the following operations can be applied on the number A:
- Select any odd integer x (x>0) and add it to A i.e. (A+x);
- Or, select any even integer y (y>0) and subtract it from A i.e. (A-y).
Examples:
Input: A = 2, B = 3
Output: 1
Explanation: Add odd x = 1 to A to obtain B (1 + 2 = 3).Input: A = 7, B = 4
Output: 2
Explanation: Two operations are required:
Subtract y = 4 from A (7 – 4 = 3).
Add x = 1 to get B (3 + 1 = 4).
Approach: This is an implementation-based problem. Follow the steps below to solve the given problem.
- Store absolute difference of A-B in variable diff.
- Check if A is equal to B. As the two integers are equal, the total number of operations will be 0.
- Else check if A < B.
- If yes, check if their difference is odd or even.
- If diff is odd, A+x operation is applied once (x is an odd integer equal to diff). The total number of operations is 1.
- Else diff is even, apply A+x operation twice, Firstly where x is diff -1 (odd) and secondly where x is 1. Or, A+x operation can be followed by A-y operation. In either case, the total number of operations will be 2.
- If yes, check if their difference is odd or even.
- Else if A> B, the opposite set of operations are applied i.e.
- If diff is even, A-y operation is applied once.
- Else A-y operation can be applied followed by A+x operation. Or, A-y operation can be applied twice.
Hence, the number of operations will always be either 0, 1, or 2.
Below is the implementation for the above approach.
C++
// C++ program for the given approach#include <bits/stdc++.h>using namespace std;// Function to find// minimum number of operationsint minOperations(int A, int B){ // Variable to store // difference of A and B int diff; if (A == B) return 0; else if (A < B) { // A+x operation first diff = B - A; if (diff % 2 != 0) return 1; return 2; } else { // A-y operation first diff = A - B; if (diff % 2 == 0) return 1; return 2; }}// Driver codeint main(){ // Declaring integers A and B int A, B; // Initialising A = 7; B = 4; // Function call int ans = minOperations(A, B); // Displaying the result cout << ans; return 0;} |
Java
// Java program for the given approachimport java.util.*;class GFG{// Function to find// minimum number of operationsstatic int minOperations(int A, int B){ // Variable to store // difference of A and B int diff; if (A == B) return 0; else if (A < B) { // A+x operation first diff = B - A; if (diff % 2 != 0) return 1; return 2; } else { // A-y operation first diff = A - B; if (diff % 2 == 0) return 1; return 2; }}// Driver codepublic static void main(String[] args){ // Declaring integers A and B int A, B; // Initialising A = 7; B = 4; // Function call int ans = minOperations(A, B); // Displaying the result System.out.print(ans);}}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach # Function to find# minimum number of operationsdef minOperations(A, B): # Variable to store # difference of A and B diff = None if (A == B): return 0; elif (A < B): # A+x operation first diff = B - A; if (diff % 2 != 0): return 1; return 2; else: # A-y operation first diff = A - B; if (diff % 2 == 0): return 1; return 2; # Driver code# Initialising A and BA = 7;B = 4;# Function callans = minOperations(A, B);# Displaying the resultprint(ans);# This code is contributed by gfgking |
C#
// C# program for the given approachusing System;class GFG{// Function to find// minimum number of operationsstatic int minOperations(int A, int B){ // Variable to store // difference of A and B int diff; if (A == B) return 0; else if (A < B) { // A+x operation first diff = B - A; if (diff % 2 != 0) return 1; return 2; } else { // A-y operation first diff = A - B; if (diff % 2 == 0) return 1; return 2; }}// Driver codepublic static void Main(){ // Declaring integers A and B int A, B; // Initialising A = 7; B = 4; // Function call int ans = minOperations(A, B); // Displaying the result Console.Write(ans);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find // minimum number of operations function minOperations(A, B) { // Variable to store // difference of A and B let diff; if (A == B) return 0; else if (A < B) { // A+x operation first diff = B - A; if (diff % 2 != 0) return 1; return 2; } else { // A-y operation first diff = A - B; if (diff % 2 == 0) return 1; return 2; } } // Driver code // Declaring integers A and B let A, B; // Initialising A = 7; B = 4; // Function call let ans = minOperations(A, B); // Displaying the result document.write(ans); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
