Given two positive integers, X and Y, the task is to find the minimum number of operations to make X and y equal where in one operation, we can select any positive integer Z and do the following process.
- If the number Z is even, subtract Z from X.
- If the number Z is odd, add Z to X.
Examples:
Input: X = 4, Y = 7
Output: 1
Explanation: Select Z = 3, then the new X will be 4 + 3 = 7.
Hence, it requires only one operation.Input: X = 6, Y = 6
Output: 0
Explanation: Both of them are already the same.
Hence, it requires 0 operations.
Approach: This problem can be solved using the Greedy approach based on the following observation:
There are only three possible answers:
- First, if X = Y, no operation is required,
- Second, If X > Y and X − Y is even or X < Y and Y − X is odd, then only 1 operation is required.
- Third, if X > Y and X − Y is odd or X < Y and Y − X is even, then there is need for 2 operations. One move extra is required for turning it to the second case
Follow the below steps to solve this problem:
- Find the relation between X and Y.
- Now based on the relation find how many moves are needed based on the above observation.
Below is the implementation of the above approach :
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of moves requiredint minMoves(int X, int Y){ // Checking if both 'X' and 'Y' // are same or not. if (X == Y) { return 0; } // Checking if we can make X and Y equal // if we select Z = X - Y else if (X > Y && (X - Y) % 2 == 0) { return 1; } // Checking if we can make X and Y equal // if we select Z = Y - X else if (X < Y && (Y - X) % 2 == 1) { return 1; } else { return 2; }}// Driver Codeint main(){ int X = 4, Y = 7; // Function call cout << minMoves(X, Y); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG{ // Function to find the minimum number // of moves required public static int minMoves(int X, int Y) { // Checking if both 'X' and 'Y' // are same or not. if (X == Y) { return 0; } // Checking if we can make X and Y equal // if we select Z = X - Y else if (X > Y && (X - Y) % 2 == 0) { return 1; } // Checking if we can make X and Y equal // if we select Z = Y - X else if (X < Y && (Y - X) % 2 == 1) { return 1; } else { return 2; } } // Driver Code public static void main(String[] args) { int X = 4, Y = 7; // Function call System.out.print(minMoves(X, Y)); }}// This code is contributed by ashishsingh13122000. |
Python3
# Python code to implement the above approach# Function to find the minimum number# of moves requireddef minMoves(X, Y): # Checking if both 'X' and 'Y' # are same or not. if (X == Y): return 0 # Checking if we can make X and Y equal # if we select Z = X - Y elif (X > Y and (X - Y) % 2 == 0): return 1 # Checking if we can make X and Y equal # if we select Z = Y - X elif (X < Y and (Y - X) % 2 == 1): return 1 else: return 2# Driver CodeX, Y = 4, 7# Function callprint(minMoves(X, Y))# This code is contributed by shinjanpatra |
C#
// C# code to implement the above approachusing System;class GFG { // Function to find the minimum number // of moves required static int minMoves(int X, int Y) { // Checking if both 'X' and 'Y' // are same or not. if (X == Y) { return 0; } // Checking if we can make X and Y equal // if we select Z = X - Y else if (X > Y && (X - Y) % 2 == 0) { return 1; } // Checking if we can make X and Y equal // if we select Z = Y - X else if (X < Y && (Y - X) % 2 == 1) { return 1; } else { return 2; } } // Driver Code public static void Main() { int X = 4, Y = 7; // Function call Console.Write(minMoves(X, Y)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the above approach // Function to find the minimum number // of moves required const minMoves = (X, Y) => { // Checking if both 'X' and 'Y' // are same or not. if (X == Y) { return 0; } // Checking if we can make X and Y equal // if we select Z = X - Y else if (X > Y && (X - Y) % 2 == 0) { return 1; } // Checking if we can make X and Y equal // if we select Z = Y - X else if (X < Y && (Y - X) % 2 == 1) { return 1; } else { return 2; } } // Driver Code let X = 4, Y = 7; // Function call document.write(minMoves(X, Y));// This code is contributed by rakeshsahni</script> |
Output
1
Time Complexity: O(1)
Auxiliary Space: O(1)
Share your thoughts in the comments
