News Leaflets
A leading news portal.

Min operations to convert A to B by incrementing A in the given range

0 22

Improve Article

Save Article

Like Article

Improve Article

Save Article

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

#include <bits/stdc++.h>

using namespace std;

#define int long long

  

int minOperations(int A, int B, int C, int D, int E)

{

  

    

    if (A == B) {

        return 0;

    }

  

    

    else if (abs(A - B) >= E) {

        return 1;

    }

  

    

    else if (D - max(A, B) >= E || min(A, B) - C >= E) {

        return 2;

    }

  

    

    else if ((D - B >= E && A - C >= E)

             || (D - A >= E && B - C >= E)) {

        return 3;

    }

  

    

    else {

        return -1;

    }

}

  

int32_t main()

{

    int A = 4, B = 5, C = 0, D = 15, E = 5;

    int answer = minOperations(A, B, C, D, E);

  

    

    cout << answer << endl;

    return 0;

}

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

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment
Immediate Unity Profit Immediate Gains ProI