in ,

Minimize operations to convert (0, 0) to (N, M) by incrementing either or both by K

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 opertation, 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++

#include

using namespace std;

  

int minOperations(int N, int M)

{

    

    if (N == M && N == 0)

        return 0;

  

    

    if (N == M)

        return 1;

  

    

    if (N % 2 == M % 2)

        return 2;

  

    

    return -1;

}

  

int main()

{

    int N = 3;

    int M = 5;

    cout << minOperations(N, M);

  

    return 0;

}

Time Complexity: O(1)
Auxiliary Space: O(1)

What do you think?

Silver 1

Written by yulica

Leave a Reply

Your email address will not be published.

      Android vs iOS Development: Pros and Cons of Each Platform_61d8c364a6197.jpeg

      Android vs iOS Development: Pros and Cons of Each Platform

      Mobile App Development Trends for 2020_61d8c2bb8874c.jpeg

      Mobile App Development Trends for 2020