Minimize value of |A – X| + |B – Y| + |C – Z| such that X * Y = Z

Solution Approach

You can easily notice that the maximum value of the expression is A+B+C if all three of X, Y, and Z are zero. As the value of the expression will be maximum when X, Y and Z are minimum and since all three of them are greater than or equal to zero, their minimum value is zero.

Now, What is the maximum value the expression X*Y can take? Since, here, X*Y = Z, we know that Z can't be greater than 2*C. And why is it so? Because then, the expression will be |A-X|+|B-Y|+|C-(>2*C)| with X*Y>2*C. And this makes the value of the expression greater than A+B+C, which is not possible. So, the maximum value of X*Y can only be 2*C, and therefore, we now have a limit on the number of values we have to check.

So, we can just run a for loop from 1 to 2*C for X and find the corresponding Y such that X*Y<=2*C and find the value of the expression. If the current value of the expression is smaller than the current minimum value, then update the minimum value to this value. 

Steps of implementation are:

• Input the values of A, B, and C.
   
• Declare a variable "ans," which will store the minimum value of the expression at any instance of time, and initialize it with INT_MAX
   
• Run through a for loop and iterate through all the values of X between 1 to 2*C
   
• Iterate through different values of Y, till X*Y<=2*C
   
• For each value of X and Y, find the value of the expression and update the value of the answer if the current expression has a smaller value than ans
   
• Print the value of ans.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int A,B,C;
    /*
        Input the values of A, B and C
    */
    A = 21, B = 16, C = 628;
    /*
        Declare a variable "ans", which will store minimum value of the
        expression at any instance of time, and initialize it with INT_MAX
    */
    int ans = INT_MAX;
    /*
      Run through a for loop and iterate through all the values of X 
       between 1 to 2*C
    */
    for(int X=1;X<=2*C;X++){
        int Y=0;
        /*
            Iterate through different values of Y, till X*Y<=2*C
        */
        while(X*Y<=2*C){
            /* 
                For each value of X and Y, find the value of the expression,
                and update the value of the answer if the current expression
                has smaller value than ans
            */
            int temp_ans = (abs(A-X)+abs(B-Y)+abs(C-(X*Y)));
            if(temp_ans<ans){
                ans = temp_ans;
            }
            Y++;
        }
    }
    /*
        Print the value of ans
    */
    cout<<ans<<endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

16

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time complexity

O(C*logC), where C is the input.

Reason: A for loop is running here for 2*C times, which takes O(C) time, and in it, there is a while loop running for logC time because it runs till X*Y<=2*C. Thus, the overall time complexity is O(C*logC).

Space complexity

O(1)

Reason: The spaces taken in the above implementation are integer variables, and thus, only take constant time.
Check out this problem - Maximum Product Subarray

Frequently asked questions

1. What is an absolute value of an integer x?
   The absolute value of an integer x is the value of its magnitude with a positive sign. The absolute value of x is denoted by |x|.
    
2. What is the function for the absolute value of x in c++?
   In c++, there is a function called "abs()," which takes the number as the parameter and returns the absolute value of the number.

Key Takeaways

In this article, we discussed the problem of finding the minimum value of the expression |A-X|+|B-Y|+|C-Z| where Z = X*Y. A problem similar to this one is the maximum value of modulus expression, so try solving it yourself.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!