Given two integers N and M, the task is to calculate the minimum number of operations required to convert (0, 0) to (N, M) using the following operations:
- Choose any integer K and convert (x, y) to (x + K, y + K).
- Choose any integer K and convert (x, y) to (x – K, y + K) or (x + K, y – K).
Examples:
Input: N = 3, M = 5
Output: 2
Explanation: In 1st operation, take K = 4, and perform 1st operation i.e, (0 + 4, 0 + 4) -> (4, 4). In 2nd operation, take K = 1 and perform 2nd operation i.e, (4 – 1, 4 + 1) -> (3, 5) which is the required value.Input: N = 1, M = 4
Output: -1
Explanation: No possible sequence of given operations exists to convert (0, 0) to (1, 4).
Approach: The given problem can be solved using the observation that each (N, M) pair can be divided into four following cases:
- Case 1, where (N, M) = (0, 0). In such cases, 0 operations will be required.
- Case 2, where N = M. In such cases, choose K = N and perform the 1st operation. Hence only one operation is required.
- Case 3, where N and M are of the same parity, i.e, N % 2 = M % 2. In such cases, it can be observed that the required number of operations is always 2.
- Case 4, where N and M are of different parity, i.e, N % 2 != M % 2. In such cases, no possible sequence of operations exists.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of operations required to convert// a pair of integers (0, 0) to (N, M)int minOperations(int N, int M){ // Case 1 if (N == M && N == 0) return 0; // Case 2 if (N == M) return 1; // Case 3 if (N % 2 == M % 2) return 2; // Not possible return -1;}// Driver Codeint main(){ int N = 3; int M = 5; cout << minOperations(N, M); return 0;} |
Java
// Java program to implement// the above approachclass GFG { // Function to find the minimum number // of operations required to convert // a pair of integers (0, 0) to (N, M) static int minOperations(int N, int M) { // Case 1 if (N == M && N == 0) return 0; // Case 2 if (N == M) return 1; // Case 3 if (N % 2 == M % 2) return 2; // Not possible return -1; } // Driver Code public static void main(String args[]) { int N = 3; int M = 5; System.out.println(minOperations(N, M)); }}// This code is contributed by Saurabh Jaiswal |
Python3
# Python program of the above approach# Function to find the minimum number# of operations required to convert# a pair of integers (0, 0) to (N, M)def minOperations(N, M): # Case 1 if N == M and N == 0: return 0 # Case 2 if N == M: return 1 # Case 3 if N % 2 == M % 2: return 2 # Not possible return -1# Driver CodeN = 3M = 5print(minOperations(N, M))# This code is contributed by GFGking |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the minimum number // of operations required to convert // a pair of integers (0, 0) to (N, M) static int minOperations(int N, int M) { // Case 1 if (N == M && N == 0) return 0; // Case 2 if (N == M) return 1; // Case 3 if (N % 2 == M % 2) return 2; // Not possible return -1; } // Driver Code public static void Main() { int N = 3; int M = 5; Console.Write(minOperations(N, M)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program of the above approach // Function to find the minimum number // of operations required to convert // a pair of integers (0, 0) to (N, M) const minOperations = (N, M) => { // Case 1 if (N == M && N == 0) return 0; // Case 2 if (N == M) return 1; // Case 3 if (N % 2 == M % 2) return 2; // Not possible return -1; } // Driver Code let N = 3; let M = 5; document.write(minOperations(N, M));// This code is contributed by rakeshsahni</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!
Share your thoughts in the comments
