Check if K can be obtained by performing arithmetic operations on any permutation of an Array
Given an array arr[] of N integers and an integer K, the task is to check if the expression formed for any permutation of the given array after assigning arithmetic operators(+, -, /, *) gives the value K or not. If found to be true, then print the order of operations performed. Otherwise, print “-1”.
Note: After division operator ‘/’ is applied, the result can be a floating-point number.
Examples:
Input: arr[] = {2, 0, 0, 2}, K = 4
Output: 2 + 0 => 2 + 2 => 4 + 0 => 4Input: arr[] = {1, 2, 4, 7}, K = 50
Output: -1
Approach: The idea is to use Backtracking and find the value of the resultant equation by generating all possible combinations of assigning the operators. Below are the steps:
- Traverse the array And choose the first two elements and apply every possible operation. Let the result of this above operation be X.
- Now, perform all possible operations on X and the next element of the array and so on.
- Repeat all the above steps until all the possible combinations of operations are performed.
- Now, if any combination of operations generates the result K, then print that combination.
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the string of// possible combination of operationsbool 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 Kvoid checkPossibleOperation( vector<double>& arr, double K){ // Store the resultant operation string s = ""; // Function Call if (!find(arr, arr.size(), K, s)) { cout << "-1"; }}// Driver Codeint 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 approachclass GFG{ // Function that finds the string of// possible combination of operationsstatic 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 Kstatic 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 Codepublic 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 operationsdef 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 Kdef checkPossibleOperation(arr, K): # Store the resultant operation s = "" # Function Call if (not find(arr, len(arr), K, s)): print ("-1")# Driver Codeif __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 approachusing System;class GFG{ // Function that finds the string of// possible combination of operationsstatic 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 Kstatic 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 Codepublic 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 operationsfunction 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 Kfunction 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 Klet K = 4;// Function callcheckPossibleOperation(arr, K);// This code is contributed by avanitrachhadiya2155</script> |
Output:
2+0 => 2+2 => 4+0 => 4
Time Complexity: O(N!*4N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
