Dada una array arr[] de N enteros y un entero K , la tarea es verificar si la expresión formada para cualquier permutación de la array dada después de asignar operadores aritméticos ( +, -, /, * ) da el valor K o no. Si es cierto, imprima el orden de las operaciones realizadas. De lo contrario, imprima «-1» .
Nota: Después de aplicar el operador de división ‘/’, el resultado puede ser un número de punto flotante.
Ejemplos:
Entrada: arr[] = {2, 0, 0, 2}, K = 4
Salida: 2 + 0 => 2 + 2 => 4 + 0 => 4Entrada: arr[] = {1, 2, 4, 7}, K = 50
Salida: -1
Enfoque: La idea es usar Backtracking y encontrar el valor de la ecuación resultante generando todas las combinaciones posibles de asignación de operadores. A continuación se muestran los pasos:
- Atraviesa la array Y elige los dos primeros elementos y aplica todas las operaciones posibles. Deje que el resultado de esta operación anterior sea X .
- Ahora, realice todas las operaciones posibles en X y el siguiente elemento de la array y así sucesivamente.
- Repita todos los pasos anteriores hasta que se realicen todas las combinaciones posibles de operaciones.
- Ahora, si cualquier combinación de operaciones genera el resultado K , imprima esa combinación.
- De lo contrario, imprima » -1″ .
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 that finds the string of
// possible combination of operations
bool find(vector<double>& v, int n,
double dest, string s)
{
// If only one number left then
// check for result
if (n == 1) {
// If resultant value is K
if (abs(v[0] - dest) <= 0.0000001) {
cout << s + to_string(int(dest))
<< " ";
return 1;
}
// Else return 0
return 0;
}
// Choose all combination of numbers
// and operators and operate them
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a = v[i], b = v[j];
// Choose the first two and
// operate it with '+'
string p = s;
v[i] = a + b;
// Place it to 0th position
v[j] = v[n - 1];
// Place (n-1)th element on
// 1st position
s = (s + to_string(int(a)) + '+'
+ to_string(int(b))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
// Now, we have N - 1 elements
s = p;
v[i] = a - b;
// Try '-' operation
v[j] = v[n - 1];
s = (s + to_string(int(a)) + '-'
+ to_string(int(b))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
s = p;
v[i] = b - a;
// Try reverse '-'
v[j] = v[n - 1];
s = (s + to_string(int(b)) + '-'
+ to_string(int(a))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
s = p;
v[i] = a * b;
// Try '*' operation
v[j] = v[n - 1];
s = (s + to_string(int(a))
+ '*'
+ to_string(int(b))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
s = p;
if (b != 0) {
v[i] = a / b;
// Try '/'
v[j] = v[n - 1];
s = (s + to_string(int(a))
+ '/'
+ to_string(int(b))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
}
s = p;
if (a != 0) {
v[i] = b / a;
// Try reverse '/'
v[j] = v[n - 1];
s = (s + to_string(int(b))
+ '/'
+ to_string(int(a))
+ " => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return 1;
}
s = p;
// Backtracking Step
v[i] = a;
v[j] = b;
}
}
// Return 0 if there doesnt exist
// any combination that gives K
return 0;
}
// Function that finds the possible
// combination of operation to get the
// resultant value K
void checkPossibleOperation(
vector<double>& arr, double K)
{
// Store the resultant operation
string s = "";
// Function Call
if (!find(arr, arr.size(), K, s)) {
cout << "-1";
}
}
// Driver Code
int main()
{
// Given array arr[]
vector<double> arr = { 2, 0, 0, 2 };
// Resultant value K
double K = 4;
// Function Call
checkPossibleOperation(arr, K);
return 0;
}
Java
// Java program for above approach
class GFG{
// Function that finds the string of
// possible combination of operations
static boolean find(double[] v, int n,
double dest, String s)
{
// If only one number left then
// check for result
if (n == 1)
{
// If resultant value is K
if (Math.abs(v[0] - dest) <= 0.0000001)
{
System.out.println(s +
String.valueOf((int)dest) + " ");
return true;
}
// Else return 0
return false;
}
// Choose all combination of numbers
// and operators and operate them
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
double a = v[i], b = v[j];
// Choose the first two and
// operate it with '+'
String p = s;
v[i] = a + b;
// Place it to 0th position
v[j] = v[n - 1];
// Place (n-1)th element on
// 1st position
s = (s + String.valueOf((int)a) +
'+' + String.valueOf((int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
// Now, we have N - 1 elements
s = p;
v[i] = a - b;
// Try '-' operation
v[j] = v[n - 1];
s = (s + String.valueOf((int)a) +
'-' + String.valueOf((int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = b - a;
// Try reverse '-'
v[j] = v[n - 1];
s = (s + String.valueOf((int)b) +
'-' + String.valueOf((int)a) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = a * b;
// Try '*' operation
v[j] = v[n - 1];
s = (s + String.valueOf((int)a) +
'*' + String.valueOf((int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
if (b != 0)
{
v[i] = a / b;
// Try '/'
v[j] = v[n - 1];
s = (s + String.valueOf((int)a) +
'/' + String.valueOf((int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
if (a != 0)
{
v[i] = b / a;
// Try reverse '/'
v[j] = v[n - 1];
s = (s + String.valueOf((int)b) +
'/' + String.valueOf((int)a) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
// Backtracking Step
v[i] = a;
v[j] = b;
}
}
// Return 0 if there doesnt exist
// any combination that gives K
return false;
}
// Function that finds the possible
// combination of operation to get the
// resultant value K
static void checkPossibleOperation(double[] arr,
double K)
{
// Store the resultant operation
String s = "";
// Function call
if (!find(arr, arr.length, K, s))
{
System.out.println("-1");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
double[] arr = { 2, 0, 0, 2 };
// Resultant value K
double K = 4;
// Function call
checkPossibleOperation(arr, K);
}
}
// This code is contributed by Dadi Madhav
Python3
# Python3 program for the above approach
# Function that finds the string of
# possible combination of operations
def find(v, n, dest, s):
# If only one number left then
# check for result
if (n == 1):
# If resultant value is K
if (abs(v[0] - dest) <= 0.0000001):
print (s + str(int(dest)) ,end = " ")
return 1
#;Else return 0
return 0
# Choose all combination of numbers
# and operators and operate them
for i in range (n):
for j in range (i + 1, n):
a = v[i]
b = v[j]
# Choose the first two and
# operate it with '+'
p = s
v[i] = a + b
# Place it to 0th position
v[j] = v[n - 1]
# Place (n-1)th element on
# 1st position
s = (s + str(int(a)) + '+' +
str(int(b)) + " => ")
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
# Now, we have N - 1 elements
s = p
v[i] = a - b
# Try '-' operation
v[j] = v[n - 1]
s = (s + str(int(a)) + '-' +
str(int(b)) +" => ")
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
s = p
v[i] = b - a
# Try reverse '-'
v[j] = v[n - 1]
s = (s + str(int(b)) + '-' +
str(int(a)) + " => ")
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
s = p
v[i] = a * b
# Try '*' operation
v[j] = v[n - 1]
s = (s + str(int(a)) + '*' +
str(int(b)) + " => ");
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
s = p
if (b != 0):
v[i] = a // b
# Try '/'
v[j] = v[n - 1]
s = (s + str(int(a)) + '/' +
str(int(b)) + " => ")
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
s = p
if (a != 0):
v[i] = b // a
# Try reverse '/'
v[j] = v[n - 1]
s = (s + str(int(b)) + '/' +
str(int(a)) + " => ")
# Evaluate the expression
# with current combination
if (find(v, n - 1, dest, s)):
return 1
s = p
# Backtracking Step
v[i] = a
v[j] = b
# Return 0 if there doesnt exist
# any combination that gives K
return 0
# Function that finds the possible
# combination of operation to get the
# resultant value K
def checkPossibleOperation(arr, K):
# Store the resultant operation
s = ""
# Function Call
if (not find(arr, len(arr), K, s)):
print ("-1")
# Driver Code
if __name__ == "__main__":
# Given array arr[]
arr = [2, 0, 0, 2]
# Resultant value K
K = 4
# Function Call
checkPossibleOperation(arr, K)
#This code is contributed by Chitranayal
C#
// C# program for
// the above approach
using System;
class GFG{
// Function that finds the string of
// possible combination of operations
static bool find(double[] v, int n,
double dest, String s)
{
// If only one number left then
// check for result
if (n == 1)
{
// If resultant value is K
if (Math.Abs(v[0] - dest) <= 0.0000001)
{
Console.WriteLine(s + String.Join("",
(int)dest) + " ");
return true;
}
// Else return 0
return false;
}
// Choose all combination of numbers
// and operators and operate them
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
double a = v[i], b = v[j];
// Choose the first two and
// operate it with '+'
String p = s;
v[i] = a + b;
// Place it to 0th position
v[j] = v[n - 1];
// Place (n-1)th element on
// 1st position
s = (s + String.Join("", (int)a) +
'+' + String.Join("", (int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
// Now, we have N - 1 elements
s = p;
v[i] = a - b;
// Try '-' operation
v[j] = v[n - 1];
s = (s + String.Join("", (int)a) +
'-' + String.Join("", (int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = b - a;
// Try reverse '-'
v[j] = v[n - 1];
s = (s + String.Join("", (int)b) +
'-' + String.Join("", (int)a) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = a * b;
// Try '*' operation
v[j] = v[n - 1];
s = (s + String.Join("", (int)a) +
'*' + String.Join("", (int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
if (b != 0)
{
v[i] = a / b;
// Try '/'
v[j] = v[n - 1];
s = (s + String.Join("", (int)a) +
'/' + String.Join("", (int)b) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
if (a != 0)
{
v[i] = b / a;
// Try reverse '/'
v[j] = v[n - 1];
s = (s + String.Join("", (int)b) +
'/' + String.Join("", (int)a) +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
// Backtracking Step
v[i] = a;
v[j] = b;
}
}
// Return 0 if there doesnt exist
// any combination that gives K
return false;
}
// Function that finds the possible
// combination of operation to get the
// resultant value K
static void checkPossibleOperation(double[] arr,
double K)
{
// Store the resultant operation
String s = "";
// Function call
if (!find(arr, arr.Length, K, s))
{
Console.WriteLine("-1");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
double[] arr = {2, 0, 0, 2};
// Resultant value K
double K = 4;
// Function call
checkPossibleOperation(arr, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for above approach
// Function that finds the string of
// possible combination of operations
function find(v,n,dest,s)
{
// If only one number left then
// check for result
if (n == 1)
{
// If resultant value is K
if (Math.abs(v[0] - dest) <= 0.0000001)
{
document.write(s +
(dest).toString() + " <br>");
return true;
}
// Else return 0
return false;
}
// Choose all combination of numbers
// and operators and operate them
for(let i = 0; i < n; i++)
{
for(let j = i + 1; j < n; j++)
{
let a = v[i], b = v[j];
// Choose the first two and
// operate it with '+'
let p = s;
v[i] = a + b;
// Place it to 0th position
v[j] = v[n - 1];
// Place (n-1)th element on
// 1st position
s = (s + a.toString() +
'+' + b.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
// Now, we have N - 1 elements
s = p;
v[i] = a - b;
// Try '-' operation
v[j] = v[n - 1];
s = (s + a.toString() +
'-' + b.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = b - a;
// Try reverse '-'
v[j] = v[n - 1];
s = (s + b.toString() +
'-' + a.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
v[i] = a * b;
// Try '*' operation
v[j] = v[n - 1];
s = (s + a.toString() +
'*' + b.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
s = p;
if (b != 0)
{
v[i] = a / b;
// Try '/'
v[j] = v[n - 1];
s = (s + a.toString() +
'/' + b.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
if (a != 0)
{
v[i] = b / a;
// Try reverse '/'
v[j] = v[n - 1];
s = (s + b.toString() +
'/' + a.toString() +
" => ");
// Evaluate the expression
// with current combination
if (find(v, n - 1, dest, s))
return true;
}
s = p;
// Backtracking Step
v[i] = a;
v[j] = b;
}
}
// Return 0 if there doesnt exist
// any combination that gives K
return false;
}
// Function that finds the possible
// combination of operation to get the
// resultant value K
function checkPossibleOperation(arr,k)
{
// Store the resultant operation
let s = "";
// Function call
if (!find(arr, arr.length, K, s))
{
document.write("-1");
}
}
// Driver Code
// Given array arr[]
let arr=[2, 0, 0, 2 ];
// Resultant value K
let K = 4;
// Function call
checkPossibleOperation(arr, K);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2+0 => 2+2 => 4+0 => 4
Complejidad de tiempo: O(N!*4 N )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA