Tuesday, 7 Dec 2021

# Find minimum value expression by inserting addition or multiplication operator between digits of given number

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 stringElse 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 characternot ‘1’ then Insert addition operator ‘+’ between the current and previous characterBelow is the implementation of the above approach:C++#include using namespace std;string minimalExpression(string str){            string ans = “”;    ans.push_back(str[0]);    bool iszero = false;            for (int i = 0; i < str.size();         i++) {        if (str[i] == '0') {            iszero = true;        }    }            if (iszero) {        for (int i = 1; i < str.size();             i++) {            ans.push_back('*');            ans.push_back(str[i]);        }        return ans;    }                for (int i = 1; i < str.size(); i++) {                                if (str[i] == '1') {            ans.push_back('*');            ans.push_back(str[i]);        }                                else {            ans.push_back('+');            ans.push_back(str[i]);        }    }        return ans;}int main(){    string str = "391118571";    cout