Dada una array arr[] que consta de N enteros positivos y una string S de longitud (N – 1) , que contiene los caracteres ‘+’ y ‘*’ , la tarea es encontrar el número más pequeño que se puede obtener después de aplicar las operaciones aritméticas mencionado en la string S en los elementos de la array en cualquier orden.
Ejemplos:
Entrada: A[] ={2, 2, 2, 2}, S = “**+”
Salida: 8
Explicación:
Operación 1: Realice la operación de multiplicación en la operación de los dos primeros elementos, es decir, arr[0]*arr[ 1] = 2*2 = 4. Ahora la array se modifica a {4, 2, 2}.
Operación 2: Realice la operación de multiplicación en los dos elementos restantes, es decir, arr[1]*arr[2] = 2*2 = 4. Ahora la array se modifica a {4, 4}.
Operación 3: Realice la operación de suma en los elementos restantes arr[0] + arr[1] = 4 + 4 = 8. Ahora la array se modifica a {8}.
Por tanto, el resultado de la operación realizada es 8, que es el mínimo.Entrada: A[] = {1, 2, 3, 4}, S = “*++”
Salida: 9
Enfoque: el problema dado se puede resolver usando un enmascaramiento de bits . Siga los pasos a continuación para resolver el problema:
- Almacene el conteo de la operación de multiplicación y suma en la string S en variables, digamos mul y suma respectivamente.
- Ahora, la operación aplicada en los elementos de la array se puede codificar en una máscara (string binaria) de modo que si se establece el i -ésimo bit de máscara, entonces es igual a ‘1’ , y se debe realizar la operación de multiplicación. De lo contrario, realice la suma.
- Inicialice una variable, digamos ans como INT_MAX que almacena el valor mínimo del resultado.
- Entonces, cree todas las máscaras en el rango [0, 2 (N – 1) ] y encuentre el número de bits establecidos en la máscara y realice los siguientes pasos:
- Si el número de bits establecidos en la máscara es igual a mul , aplique esta máscara en la array A[] , es decir, si el i -ésimo bit de la máscara es ‘1’ , realice la operación de multiplicación en el i -ésimo elemento y (i + 1) th elemento.
- De lo contrario, realice la suma.
- Actualice el valor de ans al mínimo de ans y el valor calculado en el paso anterior.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 smallest number
// that can be obtained after applying
// the arithmetic operations mentioned
// in the string S
int minimumSum(int A[], int N, string S)
{
// Stores the count of multiplication
// operator in the string
int mul = 0;
for (int i = 0;
i < (int)S.size(); i++) {
if (S[i] == '*')
mul += 1;
}
// Store the required result
int ans = 1000000;
// Iterate in the range to
// create the mask
for (int i = 0;
i < (1 << (N - 1)); i++) {
int cnt = 0;
vector<char> v;
// Checking the number of bits
// that are set in the mask
for (int j = 0; j < N - 1; j++) {
if ((1 << j) & (i)) {
cnt += 1;
v.push_back('*');
}
else {
v.push_back('+');
}
}
// Check if the number of bits
// that are set in the mask is
// multiplication operation
if (cnt == mul) {
// Storing the elements
// that is to be added
deque<int> d;
d.push_back(A[0]);
// Apply the multiplications
// operation first
for (int j = 0; j < N - 1; j++) {
// If sign is '*', then
// multiply last element
// of deque with arr[i]
if (v[j] == '*') {
int x = d.back();
d.pop_back();
x = x * A[j + 1];
// Push last multiplied
// element in the deque
d.push_back(x);
}
else {
// If the element is to
// be added, then add
// it to the deque
d.push_back(A[j + 1]);
}
}
int sum = 0;
// Add all the element of
// the deque
while (d.size() > 0) {
int x = d.front();
sum += x;
d.pop_front();
}
// Minimize the answer with
// the given sum
ans = min(ans, sum);
}
}
return ans;
}
// Driver Code
int main()
{
int A[] = { 2, 2, 2, 2 };
string S = "**+";
int N = sizeof(A) / sizeof(A[0]);
cout << minimumSum(A, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the smallest number
// that can be obtained after applying
// the arithmetic operations mentioned
// in the String S
static int minimumSum(int A[], int N, String S)
{
// Stores the count of multiplication
// operator in the String
int mul = 0;
for(int i = 0;
i < (int)S.length(); i++)
{
if (S.charAt(i) == '*')
mul += 1;
}
// Store the required result
int ans = 1000000;
// Iterate in the range to
// create the mask
for(int i = 0;
i < (1 << (N - 1)); i++)
{
int cnt = 0;
Vector<Character> v = new Vector<Character>();
// Checking the number of bits
// that are set in the mask
for(int j = 0; j < N - 1; j++)
{
if (((1 << j) & (i)) > 0)
{
cnt += 1;
v.add('*');
}
else
{
v.add('+');
}
}
// Check if the number of bits
// that are set in the mask is
// multiplication operation
if (cnt == mul)
{
// Storing the elements
// that is to be added
LinkedList<Integer> d = new LinkedList<Integer>();
d.add(A[0]);
// Apply the multiplications
// operation first
for(int j = 0; j < N - 1; j++)
{
// If sign is '*', then
// multiply last element
// of deque with arr[i]
if (v.get(j) == '*')
{
int x = d.getLast();
d.removeLast();
x = x * A[j + 1];
// Push last multiplied
// element in the deque
d.add(x);
}
else
{
// If the element is to
// be added, then add
// it to the deque
d.add(A[j + 1]);
}
}
int sum = 0;
// Add all the element of
// the deque
while (d.size() > 0)
{
int x = d.peek();
sum += x;
d.removeFirst();
}
// Minimize the answer with
// the given sum
ans = Math.min(ans, sum);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 2, 2, 2, 2 };
String S = "**+";
int N = A.length;
System.out.print(minimumSum(A, N, S));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
# Function to find the smallest number
# that can be obtained after applying
# the arithmetic operations mentioned
# in the string S
def minimumSum(A, N, S):
# Stores the count of multiplication
# operator in the string
mul = 0
for i in range(len(S)):
if (S[i] == "*"):
mul += 1
# Store the required result
ans = 1000000
# Iterate in the range to
# create the mask
for i in range(1 << (N - 1)):
cnt = 0
v = []
# Checking the number of bits
# that are set in the mask
for j in range(N - 1):
if ((1 << j) & i):
cnt += 1
v.append("*")
else:
v.append("+")
# Check if the number of bits
# that are set in the mask is
# multiplication operation
if (cnt == mul):
# Storing the elements
# that is to be added
d = []
d.append(A[0])
# Apply the multiplications
# operation first
for j in range(N - 1):
# If sign is '*', then
# multiply last element
# of deque with arr[i]
if (v[j] == "*"):
x = d[len(d) - 1]
d.pop()
x = x * A[j + 1]
# append last multiplied
# element in the deque
d.append(x)
else:
# If the element is to
# be added, then add
# it to the deque
d.append(A[j + 1])
sum = 0
# Add all the element of
# the deque
while (len(d) > 0):
x = d[0]
sum += x
d.pop(0)
# Minimize the answer with
# the given sum
ans = min(ans, sum)
return ans
# Driver Code
A = [ 2, 2, 2, 2 ]
S = "**+"
N = len(A)
print(minimumSum(A, N, S))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the smallest number
// that can be obtained after applying
// the arithmetic operations mentioned
// in the String S
static int minimumSum(int []A, int N, String S)
{
// Stores the count of multiplication
// operator in the String
int mul = 0;
for(int i = 0;
i < (int)S.Length; i++)
{
if (S[i] == '*')
mul += 1;
}
// Store the required result
int ans = 1000000;
// Iterate in the range to
// create the mask
for(int i = 0;
i < (1 << (N - 1)); i++)
{
int cnt = 0;
List<char> v = new List<char>();
// Checking the number of bits
// that are set in the mask
for(int j = 0; j < N - 1; j++)
{
if (((1 << j) & (i)) > 0)
{
cnt += 1;
v.Add('*');
}
else
{
v.Add('+');
}
}
// Check if the number of bits
// that are set in the mask is
// multiplication operation
if (cnt == mul)
{
// Storing the elements
// that is to be added
List<int> d = new List<int>();
d.Add(A[0]);
// Apply the multiplications
// operation first
for(int j = 0; j < N - 1; j++)
{
// If sign is '*', then
// multiply last element
// of deque with arr[i]
if (v[j] == '*')
{
int x = d[d.Count-1];
d.RemoveAt(d.Count-1);
x = x * A[j + 1];
// Push last multiplied
// element in the deque
d.Add(x);
}
else
{
// If the element is to
// be added, then add
// it to the deque
d.Add(A[j + 1]);
}
}
int sum = 0;
// Add all the element of
// the deque
while (d.Count > 0)
{
int x = d[0];
sum += x;
d.RemoveAt(0);
}
// Minimize the answer with
// the given sum
ans = Math.Min(ans, sum);
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 2, 2, 2, 2 };
String S = "**+";
int N = A.Length;
Console.Write(minimumSum(A, N, S));
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find the smallest number
// that can be obtained after applying
// the arithmetic operations mentioned
// in the string S
function minimumSum(A, N, S)
{
// Stores the count of multiplication
// operator in the string
let mul = 0;
for(let i = 0; i < S.length; i++)
{
if (S[i] == "*")
mul += 1;
}
// Store the required result
let ans = 1000000;
// Iterate in the range to
// create the mask
for(let i = 0; i < 1 << (N - 1); i++)
{
let cnt = 0;
let v = [];
// Checking the number of bits
// that are set in the mask
for(let j = 0; j < N - 1; j++)
{
if ((1 << j) & i)
{
cnt += 1;
v.push("*");
} else
{
v.push("+");
}
}
// Check if the number of bits
// that are set in the mask is
// multiplication operation
if (cnt == mul)
{
// Storing the elements
// that is to be added
let d = [];
d.push(A[0]);
// Apply the multiplications
// operation first
for(let j = 0; j < N - 1; j++)
{
// If sign is '*', then
// multiply last element
// of deque with arr[i]
if (v[j] == "*")
{
let x = d[d.length - 1];
d.pop();
x = x * A[j + 1];
// Push last multiplied
// element in the deque
d.push(x);
}
else
{
// If the element is to
// be added, then add
// it to the deque
d.push(A[j + 1]);
}
}
let sum = 0;
// Add all the element of
// the deque
while (d.length > 0)
{
let x = d[0];
sum += x;
d.shift();
}
// Minimize the answer with
// the given sum
ans = Math.min(ans, sum);
}
}
return ans;
}
// Driver Code
let A = [ 2, 2, 2, 2 ];
let S = "**+";
let N = A.length;
document.write(minimumSum(A, N, S));
// This code is contributed by gfgking
</script>
Producción:
8
Complejidad de Tiempo: O(2 (N – 1) *N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por samarpitsmarty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA