Given string str that contains only digits, the task is to return an expression by inserting the ‘+’ or ‘*’ operator between every two digits such that the arithmetic value of the expression is minimized.
Example:
Input: str = “322”
Output: “3+2*2”
Explanation: The value of above expression is 7 which is minimum possible over the other expressions “3+2+2”, “3*2+2”, “3*3*2”Input: str = “391118571”
Output: “3+9*1*1*1+8+5+7*1”
Approach: The given problem can be solved using a greedy approach. Follow the steps below to solve the problem:
- If the string str contains character ‘0’ then:
- Insert multiplication operator between every character of the string
- Else create a string ans to store the iterate the string and if the current character str[i] is:
- ‘1’, then Insert multiplication operator ‘*’ between the current and previous character
- not ‘1’ then Insert addition operator ‘+’ between the current and previous character
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;string minimalExpression(string str){ // Initialize an empty string // to store the answer string ans = ""; ans.push_back(str[0]); bool iszero = false; // Check if zero is present in the // string for (int i = 0; i < str.size(); i++) { if (str[i] == '0') { iszero = true; } } // Insert all multiplication operators // between every digit of the string if (iszero) { for (int i = 1; i < str.size(); i++) { ans.push_back('*'); ans.push_back(str[i]); } return ans; } // Else calculate minimum expression // with combination of '*' and '+' // operators between digits for (int i = 1; i < str.size(); i++) { // If current character is '1' insert // multiplication operator between // current and previous character if (str[i] == '1') { ans.push_back('*'); ans.push_back(str[i]); } // Else insert addition operator // between current and // previous character else { ans.push_back('+'); ans.push_back(str[i]); } } // Return the result return ans;}// Driver Codeint main(){ string str = "391118571"; cout << minimalExpression(str);} |
Java
// Java implementation for the above approachclass GFG { public static String minimalExpression(String str) { // Initialize an empty String // to store the answer String ans = ""; ans = ans + str.charAt(0); boolean iszero = false; // Check if zero is present in the // String for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '0') { iszero = true; } } // Insert all multiplication operators // between every digit of the String if (iszero) { for (int i = 1; i < str.length(); i++) { ans += '*'; ans += str.charAt(i); } return ans; } // Else calculate minimum expression // with combination of '*' and '+' // operators between digits for (int i = 1; i < str.length(); i++) { // If current character is '1' insert // multiplication operator between // current and previous character if (str.charAt(i) == '1') { ans += '*'; ans += str.charAt(i); } // Else insert addition operator // between current and // previous character else { ans += '+'; ans += str.charAt(i); } } // Return the result return ans; } // Driver Code public static void main(String args[]) { String str = "391118571"; System.out.println(minimalExpression(str)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python implementation for the above approachdef minimalExpression(str): # Initialize an empty string # to store the answer ans = "" ans += str[0] iszero = False # Check if zero is present in the # string for i in range(0, len(str)): if (str[i] == '0'): iszero = True # Insert all multiplication operators # between every digit of the string if (iszero): for i in range(1, len(str)): ans += '*' ans += str[i] return ans # Else calculate minimum expression # with combination of '*' and '+' # operators between digits for i in range(1, len(str)): # If current character is '1' insert # multiplication operator between # current and previous character if (str[i] == '1'): ans += '*' ans += str[i] # Else insert addition operator # between current and # previous character else: ans += '+' ans += str[i] # Return the result return ans# Driver Codeif __name__ == "__main__": str = "391118571" print(minimalExpression(str))# This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;class GFG { static string minimalExpression(string str) { // Initialize an empty string // to store the answer string ans = ""; ans += str[0]; bool iszero = false; // Check if zero is present in the // string for (int i = 0; i < str.Length; i++) { if (str[i] == '0') { iszero = true; } } // Insert all multiplication operators // between every digit of the string if (iszero) { for (int i = 1; i < str.Length; i++) { ans += '*'; ans += (str[i]); } return ans; } // Else calculate minimum expression // with combination of '*' and '+' // operators between digits for (int i = 1; i < str.Length; i++) { // If current character is '1' insert // multiplication operator between // current and previous character if (str[i] == '1') { ans += '*'; ans += (str[i]); } // Else insert addition operator // between current and // previous character else { ans += '+'; ans += (str[i]); } } // Return the result return ans; } // Driver Code public static void Main() { string str = "391118571"; Console.WriteLine(minimalExpression(str)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript implementation for the above approachfunction minimalExpression(str) { // Initialize an empty string // to store the answer let ans = []; ans.push(str[0]); let iszero = false; // Check if zero is present in the // string for (let i = 0; i < str.length; i++) { if (str[i] == "0") { iszero = true; } } // Insert all multiplication operators // between every digit of the string if (iszero) { for (let i = 1; i < str.length; i++) { ans.push("*"); ans.push(str[i]); } return ans; } // Else calculate minimum expression // with combination of '*' and '+' // operators between digits for (let i = 1; i < str.length; i++) { // If current character is '1' insert // multiplication operator between // current and previous character if (str[i] == "1") { ans.push("*"); ans.push(str[i]); } // Else insert addition operator // between current and // previous character else { ans.push("+"); ans.push(str[i]); } } // Return the result return ans.join("");}// Driver Codelet str = "391118571";document.write(minimalExpression(str));// This code is contributed by saurabh_jaiswal.</script> |
Output
3+9*1*1*1+8+5+7*1
Time Complexity: O(N)
Auxiliary Space: O(N), where N is the length of the given string
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
