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

Output: 

2

 

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


 


Reffered: https://www.geeksforgeeks.org

Recursion

Related
C program to create copy of a singly Linked List using Recursion C program to create copy of a singly Linked List using Recursion
Print even and odd numbers in a given range using recursion Print even and odd numbers in a given range using recursion
N digit numbers having difference between the first and last digits as K N digit numbers having difference between the first and last digits as K
Check if given Binary string follows then given condition or not Check if given Binary string follows then given condition or not
Find the Nth row in Pascal&#039;s Triangle Find the Nth row in Pascal&#039;s Triangle

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje