Dados tres enteros A, B, C que denotan un triplete y tres enteros P, Q, R que denotan otro triplete. Seleccione repetidamente cualquier número entero y agréguelo o multiplíquelo a todos los elementos en un subconjunto (A, B, C) con ese número entero hasta que los dos tripletes dados sean iguales. La tarea es encontrar el número mínimo de tales operaciones requeridas para hacer que los dos tripletes sean iguales.
Ejemplo:
Entrada: (A, B, C) = (3, 4, 5), (P, Q, R) = (6, 3, 10) Salida: 2 Explicación: Paso 1: Multiplique 2 con
todos los
elementos
del subconjunto { 3, 5}. El triplete (A, B, C) se convierte en (6, 4, 10).
Paso 2: agregue -1 al subconjunto {4}. El triplete (A, B, C) se convierte en (6, 3, 10), que es lo mismo que el triplete (P, Q, R).
Por lo tanto, el número mínimo de operaciones requeridas es 2.Entrada: (A, B, C) = (7, 6, 8), (p, q, r) = (2, 2, 2) Salida: 2 Explicación: Paso 1: Multiplica
todos los
elementos
del subconjunto (7, 6, 8) con 0. (A, B, C) se modifica a (0, 0, 0).
Paso 2: agregue 2 a todos los elementos del subconjunto (0, 0, 0). (A, B, C) se modifica a (2, 2, 2) igual que el triplete (P, Q, R).
Por lo tanto, el número mínimo de operaciones requeridas es 2.
Enfoque: siga los pasos a continuación para resolver el problema dado:
- En cada paso, sume o multiplique un número entero a un subconjunto del triplete. El entero se puede elegir como:
- Además: en cada paso, intente corregir al menos uno de los números. Por lo tanto, el conjunto de todos los números posibles que deben intentarse sumar está restringido a (B[i] – A[i]) para al menos una i.
- En Multiplicación: siguiendo la misma lógica, multiplique m a un subconjunto tal que para al menos un i, se satisfaga A[i]*m = B[i] .
- Hasta ahora, todas las operaciones tenían la suposición subyacente de que después de la operación, al menos uno de los valores de A[i] se convierte en B[i].
Considere el siguiente caso: A[] = [2, 3, 4] y B[] = [-20, – 1, 18]
La transformación anterior se puede realizar en solo dos pasos multiplicando todos los números por 19 y luego sumando : 58 a cada número.
Tales casos deben ser atendidos por separado.
- Por lo tanto, use la recursividad para resolver el problema que se ocupa de todos los casos extremos y nos dará el número mínimo de operaciones que se realizarán para la conversión.
- Imprima el recuento mínimo de pasos después de los pasos anteriores.
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;
// Utility function to check whether
// given two triplets are equal or not
bool equal(int a[], int b[])
{
for (int i = 0; i < 3; i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
// Utility function to find the number
// to be multiplied such that
// their differences become equal
int mulFac(int a, int b, int c, int d)
{
if (b != a and (d - c) % (b - a) == 0) {
return (d - c) / (b - a);
}
else {
return 1;
}
}
// Function to find minimum operations
void getMinOperations(int a[], int b[],
int& ans, int num = 0)
{
// Base Case
if (num >= ans)
return;
// If triplets are converted
if (equal(a, b)) {
ans = min(ans, num);
return;
}
// Maximum possible ans is 3
if (num >= 2)
return;
// Possible values that can be
// added in next operation
set<int> add;
add.insert(b[0] - a[0]);
add.insert(b[1] - a[1]);
add.insert(b[2] - a[2]);
// Possible numbers that we can
// multiply in next operation
set<int> mult;
for (int i = 0; i < 3; i++) {
// b[i] should be divisible by a[i]
if (a[i] != 0
&& b[i] % a[i] == 0) {
mult.insert(b[i] / a[i]);
}
}
// Multiply integer to any 2 numbers
// such that after multiplication
// their difference becomes equal
mult.insert(mulFac(a[0], a[1],
b[0], b[1]));
mult.insert(mulFac(a[2], a[1],
b[2], b[1]));
mult.insert(mulFac(a[0], a[2],
b[0], b[2]));
mult.insert(0);
// Possible subsets from triplet
for (int mask = 1; mask <= 7; mask++) {
// Subset to apply operation
vector<int> subset;
for (int j = 0; j < 3; j++)
if (mask & (1 << j))
subset.push_back(j);
// Apply addition on chosen subset
for (auto x : add) {
int temp[3];
for (int j = 0; j < 3; j++)
temp[j] = a[j];
for (auto e : subset)
temp[e] += x;
// Recursively find all
// the operations
getMinOperations(temp, b,
ans, num + 1);
}
// Applying multiplication
// on chosen subset
for (auto x : mult) {
int temp[3];
for (int j = 0; j < 3; j++)
temp[j] = a[j];
for (auto e : subset)
temp[e] *= x;
// Recursively find all
// the operations
getMinOperations(temp, b,
ans, num + 1);
}
}
}
// Driver Code
int main()
{
// Initial triplet
int a[] = { 4, 5, 6 };
// Final Triplet
int b[] = { 0, 1, 0 };
// Maximum possible answer = 3
int ans = 3;
// Function Call
getMinOperations(a, b, ans);
cout << ans << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
static int ans_max = 0;
// Utility function to check whether
// given two triplets are equal or not
static boolean equal(int[] a, int[] b)
{
for(int i = 0; i < 3; i++)
{
if (a[i] != b[i])
{
return false;
}
}
return true;
}
// Utility function to find the number
// to be multiplied such that
// their differences become equal
static int mulFac(int a, int b,
int c, int d)
{
if (b != a && (d - c) % (b - a) == 0)
{
return (d - c) / (b - a);
}
else
{
return 1;
}
}
// Function to find minimum operations
static void getMinOperations(int[] a, int[] b,
int ans, int num)
{
// Base Case
if (num >= ans)
{
return;
}
// If triplets are converted
if (equal(a, b))
{
ans = Math.min(ans, num);
ans_max = ans;
return;
}
// Maximum possible ans is 3
if (num >= 2)
{
return;
}
// Possible values that can be
// added in next operation
Set<Integer> ad = new HashSet<Integer>();
ad.add(b[0] - a[0]);
ad.add(b[1] - a[1]);
ad.add(b[2] - a[2]);
// Possible numbers that we can
// multiply in next operation
Set<Integer> mult = new HashSet<Integer>();
for(int i = 0; i < 3; i++)
{
// b[i] should be divisible by a[i]
if (a[i] != 0 && b[i] % a[i] == 0)
{
mult.add(b[i] / a[i]);
}
}
// Multiply integer to any 2 numbers
// such that after multiplication
// their difference becomes equal
mult.add(mulFac(a[0], a[1],
b[0], b[1]));
mult.add(mulFac(a[2], a[1],
b[2], b[1]));
mult.add(mulFac(a[0], a[2],
b[0], b[2]));
mult.add(0);
// Possible subsets from triplet
for(int mask = 1; mask <= 7; mask++)
{
// Subset to apply operation
Vector<Integer> subset = new Vector<Integer>();
for(int j = 0; j < 3; j++)
{
if ((mask & (1 << j)) != 0)
{
subset.add(j);
}
}
// Apply addition on chosen subset
for(int x : ad)
{
int[] temp = new int[3];
for(int j = 0; j < 3; j++)
{
temp[j] = a[j];
}
for(int e:subset)
{
temp[e] += x;
}
// Recursively find all
// the operations
getMinOperations(temp, b, ans,
num + 1);
}
// Applying multiplication
// on chosen subset
for(int x:mult)
{
int[] temp = new int[3];
for(int j = 0; j < 3; j++)
{
temp[j] = a[j];
}
for(int e:subset)
{
temp[e] *= x;
}
// Recursively find all
// the operations
getMinOperations(temp, b,
ans, num + 1);
}
}
}
// Driver Code
public static void main(String[] args)
{
// Initial triplet
int[] a = { 4, 5, 6 };
// Final Triplet
int[] b = { 0, 1, 0 };
// Maximum possible answer = 3
int ans = 3;
// Function Call
getMinOperations(a, b, ans, 0);
System.out.println(ans_max);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach
ans_max = 0
# Utility function to check whether
# given two triplets are equal or not
def equal(a, b):
for i in range(3):
if (a[i] != b[i]):
return False
return True
# Utility function to find the number
# to be multiplied such that
# their differences become equal
def mulFac(a, b, c, d):
if (b != a and (d - c) % (b - a) == 0):
return (d - c) // (b - a)
else:
return 1
# Function to find minimum operations
def getMinOperations(a, b, ans, num):
global ans_max
# Base Case
if (num >= ans):
return 0
# If triplets are converted
if (equal(a, b)):
ans = min(ans, num)
ans_max = ans
return ans
# Maximum possible ans is 3
if (num >= 2):
return 0
# Possible values that can be
# added in next operation
add = {}
add[(b[0] - a[0])] = 1
add[(b[1] - a[1])] = 1
add[(b[2] - a[2])] = 1
# Possible numbers that we can
# multiply in next operation
mult = {}
for i in range(3):
# b[i] should be divisible by a[i]
if (a[i] != 0 and b[i] % a[i] == 0):
mult[b[i] // a[i]] = 1
# Multiply integer to any 2 numbers
# such that after multiplication
# their difference becomes equal
mult[mulFac(a[0], a[1], b[0], b[1])] = 1
mult[mulFac(a[2], a[1], b[2], b[1])] = 1
mult[mulFac(a[0], a[2], b[0], b[2])] = 1
mult[0] = 1
# Possible subsets from triplet
for mask in range(1, 8):
# Subset to apply operation
subset = {}
for j in range(3):
if (mask & (1 << j)):
subset[j] = 1
# Apply addition on chosen subset
for x in add:
temp = [0] * 3
for j in range(3):
temp[j] = a[j]
for e in subset:
temp[e] += x
# Recursively find all
# the operations
getMinOperations(temp, b, ans,
num + 1)
# Applying multiplication
# on chosen subset
for x in mult:
temp = [0] * 3
for j in range(3):
temp[j] = a[j]
for e in subset:
temp[e] *= x
# Recursively find all
# the operations
getMinOperations(temp, b, ans,
num + 1)
return ans
# Driver Code
if __name__ == '__main__':
# Initial triplet
a = [ 4, 5, 6 ]
# Final Triplet
b = [ 0, 1, 0 ]
# Maximum possible answer = 3
ans = 3
# Function Call
ans = getMinOperations(a, b, ans, 0)
print(ans_max)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int ans_max = 0;
// Utility function to check whether
// given two triplets are equal or not
static bool equal(int[] a, int[] b)
{
for(int i = 0; i < 3; i++)
{
if (a[i] != b[i])
{
return false;
}
}
return true;
}
// Utility function to find the number
// to be multiplied such that
// their differences become equal
static int mulFac(int a, int b,int c, int d)
{
if (b != a && (d - c) % (b - a) == 0)
{
return (d - c) / (b - a);
}
else
{
return 1;
}
}
// Function to find minimum operations
static void getMinOperations(int[] a, int[] b,int ans, int num)
{
// Base Case
if (num >= ans)
{
return;
}
// If triplets are converted
if (equal(a, b))
{
ans = Math.Min(ans, num);
ans_max = ans;
return;
}
// Maximum possible ans is 3
if (num >= 2)
{
return;
}
// Possible values that can be
// added in next operation
HashSet<int> ad = new HashSet<int>();
ad.Add(b[0] - a[0]);
ad.Add(b[1] - a[1]);
ad.Add(b[2] - a[2]);
// Possible numbers that we can
// multiply in next operation
HashSet<int> mult = new HashSet<int>();
for(int i = 0; i < 3; i++)
{
// b[i] should be divisible by a[i]
if (a[i] != 0 && b[i] % a[i] == 0)
{
mult.Add(b[i] / a[i]);
}
}
// Multiply integer to any 2 numbers
// such that after multiplication
// their difference becomes equal
mult.Add(mulFac(a[0], a[1], b[0], b[1]));
mult.Add(mulFac(a[2], a[1], b[2], b[1]));
mult.Add(mulFac(a[0], a[2], b[0], b[2]));
mult.Add(0);
// Possible subsets from triplet
for(int mask = 1; mask <= 7; mask++)
{
// Subset to apply operation
List<int> subset=new List<int>();
for(int j = 0; j < 3; j++)
{
if ((mask & (1 << j)) != 0)
{
subset.Add(j);
}
}
// Apply addition on chosen subset
foreach(int x in ad)
{
int[] temp = new int[3];
for(int j = 0; j < 3; j++)
{
temp[j] = a[j];
}
foreach(int e in subset)
{
temp[e] += x;
}
// Recursively find all
// the operations
getMinOperations(temp, b, ans,num + 1);
}
// Applying multiplication
// on chosen subset
foreach(int x in mult)
{
int[] temp = new int[3];
for(int j = 0; j < 3; j++)
{
temp[j] = a[j];
}
foreach(int e in subset)
{
temp[e] *= x;
}
// Recursively find all
// the operations
getMinOperations(temp, b,ans, num + 1);
}
}
}
// Driver Code
static public void Main ()
{
// Initial triplet
int[] a = { 4, 5, 6 };
// Final Triplet
int[] b = { 0, 1, 0 };
// Maximum possible answer = 3
int ans = 3;
// Function Call
getMinOperations(a, b, ans, 0);
Console.WriteLine(ans_max);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
let ans_max = 0;
// Utility function to check whether
// given two triplets are equal or not
function equal(a, b)
{
for(let i = 0; i < 3; i++)
{
if (a[i] != b[i])
{
return false;
}
}
return true;
}
// Utility function to find the number
// to be multiplied such that
// their differences become equal
function mulFac(a, b, c, d)
{
if (b != a && (d - c) % (b - a) == 0)
{
return (d - c) / (b - a);
}
else
{
return 1;
}
}
// Function to find minimum operations
function getMinOperations(a, b, ans, num)
{
// Base Case
if (num >= ans)
{
return;
}
// If triplets are converted
if (equal(a, b))
{
ans = Math.min(ans, num);
ans_max = ans;
return;
}
// Maximum possible ans is 3
if (num >= 2)
{
return;
}
// Possible values that can be
// added in next operation
let ad = new Set();
ad.add(b[0] - a[0]);
ad.add(b[1] - a[1]);
ad.add(b[2] - a[2]);
// Possible numbers that we can
// multiply in next operation
let mult = new Set();
for(let i = 0; i < 3; i++)
{
// b[i] should be divisible by a[i]
if (a[i] != 0 && b[i] % a[i] == 0)
{
mult.add(b[i] / a[i]);
}
}
// Multiply integer to any 2 numbers
// such that after multiplication
// their difference becomes equal
mult.add(mulFac(a[0], a[1],
b[0], b[1]));
mult.add(mulFac(a[2], a[1],
b[2], b[1]));
mult.add(mulFac(a[0], a[2],
b[0], b[2]));
mult.add(0);
// Possible subsets from triplet
for(let mask = 1; mask <= 7; mask++)
{
// Subset to apply operation
let subset = [];
for(let j = 0; j < 3; j++)
{
if ((mask & (1 << j)) != 0)
{
subset.push(j);
}
}
// Apply addition on chosen subset
for(let x of ad.values())
{
let temp = new Array(3);
for(let j = 0; j < 3; j++)
{
temp[j] = a[j];
}
for(let e = 0; e < subset.length; e++)
{
temp[subset[e]] += x;
}
// Recursively find all
// the operations
getMinOperations(temp, b, ans,
num + 1);
}
// Applying multiplication
// on chosen subset
for(let x of mult.values())
{
let temp = new Array(3);
for(let j = 0; j < 3; j++)
{
temp[j] = a[j];
}
for(let e = 0; e < subset.length; e++)
{
temp[subset[e]] *= x;
}
// Recursively find all
// the operations
getMinOperations(temp, b,
ans, num + 1);
}
}
}
// Driver Code
let a = [ 4, 5, 6 ];
let b = [ 0, 1, 0 ];
let ans = 3;
// Function Call
getMinOperations(a, b, ans, 0);
document.write(ans_max);
// This code is contributed by unknown2108
</script>
Producción:
2
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)