Minimize subset addition or multiplication to make two given triplets equal
Given three integers A, B, C denoting a triplet and three integers P, Q, R denoting another triplet. Repeatedly select any integer and add or multiply it to all elements in a subset (A, B, C) with that integer until the two given triplets become equal. The task is to find the minimum number of such operations required to make the two triplets equal.
Example:
Input: (A, B, C) = (3, 4, 5), (P, Q, R) = (6, 3, 10)
Output: 2
Explanation:
Step 1: Multiply 2 with all elements of the subset {3, 5}. Triplet (A, B, C) becomes (6, 4, 10).
Step 2: Add -1 to the subset {4}. Triplet (A, B, C) becomes (6, 3, 10) which is same as the triplet (P, Q, R).
Therefore, the minimum number of operations required is 2.Input: (A, B, C) = (7, 6, 8), (p, q, r) = (2, 2, 2)
Output: 2
Explanation:
Step 1: Multiply all elements of the subset (7, 6, 8) with 0. (A, B, C) modifies to (0, 0, 0).
Step 2: Add 2 to all elements of the subset (0, 0, 0). (A, B, C) modifies to (2, 2, 2) same as the triplet (P, Q, R).
Therefore, the minimum number of operations required is 2.
Approach: Follow the steps below to solve the given problem:
- In each step, either add or multiply an integer to a subset of the triplet. The integer can be chosen as:
- In Addition: In each step, try to fix at least one of the numbers. Hence, the set of all possible numbers that needs to be tried to add is restricted to (B[i] – A[i]) for at least one i.
- In Multiplication: Following the same logic, multiply m to a subset such that for at least one i, A[i]*m = B[i] is satisfied.
- So far, all the operations had the underlying assumption that after the operation, at least one of the values of A[i] is converted to B[i].
Consider the following Case: A[] = [2, 3, 4] and B[] = [-20, – 1, 18]
The above transformation can be done in just two steps by multiplying all numbers by 19 and then adding -58 to each number.
Such cases have to be taken care of separately.
- Therefore, use recursion to solve the problem which takes care of all the edge cases and will give us the minimum numbers of operations to be performed for the conversion.
- Print the minimum count of steps after the above steps.
Below is the implementation of the above approach:
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> |
2
Time Complexity: O(1)
Auxiliary Space: O(1)