Dados tres enteros A , B y C , la tarea es encontrar el valor mínimo posible de |A – X| + |B – Y| + |C – Z| tal que X * Y = Z .
Ejemplo :
Entrada: A = 19, B = 28, C = 522
Salida: 2
Explicación: La elección más óptima de X, Y y Z para los A, B y C dados son X = 18, Y = 29 y Z = 522. La ecuación X * Y = Z se cumple y el valor de |A – X| + |B – Y| + |C – Z| = 2 que es el mínimo posible.Entrada: A = 11, B = 11, C = 121
Salida: 0
Explicación: Los valores dados de A, B y C satisfacen A * B = C. Por lo tanto, la opción más óptima es X = A, Y = B y Z = C.
Enfoque: El problema anterior se puede resolver utilizando las siguientes observaciones:
- El valor máximo de |A – X| + |B – Y| + |C – Z| puede ser A + B + C para X , Y y Z igual a 0 .
- Con base en la observación anterior, iterar sobre todos los valores de i * j de modo que i * j <= 2 * C y elegir el mejor valor es la opción óptima.
Por lo tanto, itere sobre todos los valores de i en el rango [1, 2*C] , y para cada i , itere sobre todos los valores de j tales que i * j <= 2 * C y realice un seguimiento del valor mínimo posible de | A – yo| + |B – j| + |C – yo * j| .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum possible
// value of |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z for given A, B and C
int minimizeCost(int A, int B, int C)
{
// Stores the minimum value of
// |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z
int ans = A + B + C;
// Iterate over all values of i
// in the range [1, 2*C]
for (int i = 1; i <= 2 * C; i++) {
int j = 0;
// Iterate over all values of
// j such that i*j <= 2*c
while (i * j <= 2 * C) {
// Update the value of ans
ans = min(ans, abs(A - i) + abs(B - j)
+ abs(i * j - C));
j++;
}
}
// Return answer
return ans;
}
// Driver Code
int main()
{
int A = 19, B = 28, C = 522;
cout << minimizeCost(A, B, C);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the minimum possible
// value of |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z for given A, B and C
public static int minimizeCost(int A, int B, int C)
{
// Stores the minimum value of
// |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z
int ans = A + B + C;
// Iterate over all values of i
// in the range [1, 2*C]
for (int i = 1; i <= 2 * C; i++) {
int j = 0;
// Iterate over all values of
// j such that i*j <= 2*c
while (i * j <= 2 * C) {
// Update the value of ans
ans = Math.min(ans, Math.abs(A - i) + Math.abs(B - j)
+ Math.abs(i * j - C));
j++;
}
}
// Return answer
return ans;
}
// Driver Code
public static void main(String args[])
{
int A = 19, B = 28, C = 522;
System.out.print(minimizeCost(A, B, C));
}
}
// This code is contributed by gfgking.
Python3
# Python Program to implement # the above approach # Function to find the minimum possible # value of |A - X| + |B - Y| + |C - Z| # such that X * Y = Z for given A, B and C def minimizeCost(A, B, C): # Stores the minimum value of # |A - X| + |B - Y| + |C - Z| # such that X * Y = Z ans = A + B + C # Iterate over all values of i # in the range [1, 2*C] for i in range(1, 2 * C + 1): j = 0 # Iterate over all values of # j such that i*j <= 2*c while (i * j <= 2 * C): # Update the value of ans ans = min(ans, abs(A - i) + abs(B - j) + abs(i * j - C)) j += 1 # Return answer return ans # Driver Code A = 19 B = 28 C = 522 print(minimizeCost(A, B, C)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum possible
// value of |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z for given A, B and C
public static int minimizeCost(int A, int B, int C)
{
// Stores the minimum value of
// |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z
int ans = A + B + C;
// Iterate over all values of i
// in the range [1, 2*C]
for (int i = 1; i <= 2 * C; i++) {
int j = 0;
// Iterate over all values of
// j such that i*j <= 2*c
while (i * j <= 2 * C) {
// Update the value of ans
ans = Math.Min(ans, Math.Abs(A - i) + Math.Abs(B - j)
+ Math.Abs(i * j - C));
j++;
}
}
// Return answer
return ans;
}
// Driver Code
public static void Main(String []args)
{
int A = 19, B = 28, C = 522;
Console.Write(minimizeCost(A, B, C));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum possible
// value of |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z for given A, B and C
function minimizeCost(A, B, C)
{
// Stores the minimum value of
// |A - X| + |B - Y| + |C - Z|
// such that X * Y = Z
let ans = A + B + C;
// Iterate over all values of i
// in the range [1, 2*C]
for (let i = 1; i <= 2 * C; i++) {
let j = 0;
// Iterate over all values of
// j such that i*j <= 2*c
while (i * j <= 2 * C) {
// Update the value of ans
ans = Math.min(ans, Math.abs(A - i) + Math.abs(B - j)
+ Math.abs(i * j - C));
j++;
}
}
// Return answer
return ans;
}
// Driver Code
let A = 19, B = 28, C = 522;
document.write(minimizeCost(A, B, C));
// This code is contributed by Potta Lokesh
</script>
2
Complejidad temporal: O(C*log C)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA