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

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 Code
int main()
{
    string str = "391118571";
    cout << minimalExpression(str);
}

Java

// Java implementation for the above approach
class 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 approach
def 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 Code
if __name__ == "__main__":
 
    str = "391118571"
    print(minimalExpression(str))
 
# This code is contributed by rakeshsahni

C#

// C# implementation for the above approach
 
using 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 approach
 
function 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 Code
 
let 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

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Check if a number can be represented as sum of two positive perfect biquadrates
Program to Subtract two integers of given base
Generate N Random Hexadecimal Numbers
Find the next number by adding natural numbers in order on alternating indices from last
Find all duplicate and missing numbers in given permutation array of 1 to N

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11