The smallest number that can be obtained by applying the "+" and "*" operations to the array elements

Problem Statement

We are given an array of length "N" containing some positive integers. In addition, we are given a string of length "N-1", containing only "*" and " " characters, where "*" is the multiplication operator and " " is the addition operator. We are asked to perform an arithmetic operation on the array elements to obtain the smallest positive integer value.

Example

enter

array = [1,2,3], str = “*+”

Output

5

illustrate

It is the result value of ((1*2) 3).

enter

array = [3, 3, 3, 3], str = ‘*++’

Output

15

illustrate

It executes array[0]*array[1], which is equal to 9, and represents the result 1. After that, it adds result1 to array[2], equals 12, and represents it as result2. Next, it adds result2 to array [3], equal to 15.

enter

array =  [1, 3, 5, 6], str = “**+”

Output

21

illustrate

It is the result value of ((1*3*5) 6).

method one

We will use bit masking to solve the problem in this method.

Whenever we have two choices, we can use bit masks. Here we ask to apply arithmetic operations in any order but we need to choose between multiplication and arithmetic operations for a given string

Thus, bit masks allow us to obtain all possible ways to arrange two arithmetic operators. Afterwards, we can perform arithmetic operations on each way and check if the result is the minimum value.

Let us make the above logic clear with example input. In the example below, array = [1. 3, 5, 6], string = "*".

Here, the string length is 3. Therefore, we can have a total of 8 (2^3) bit masks, namely 000, 001, 010, 100, 110, 101, 011, 111.

Now, if we assume that "1" is "*" and "0" is " " operator, we can get all the permutations of arithmetic operators given in the string.

However, we should use any permutation only when the total number of "1"s is equal to the number of "*" operators, and the number of "0"s is equal to the number of " " operators.

algorithm

Users should follow the following algorithm to implement the above method.

• Step 1 - Define the "totalMul" variable and initialize it to zero to store the total number of multiplicative arithmetic operators in the string.

• Step 2 - Iterate over the given string using a for loop. If the current character is equal to "*", the value of the "totalMul" variable is increased by 1.

• Step 3 - Use a for loop to get all possible bit masks when X is equal to the length of the string. Here, 'len' is the array length and 'len - 1' is the string length.

• Step 4 - Define the "setBitCount" variable to store the number of bits set in the current mask. Additionally, an "order" list is defined to store the current order of arithmetic operations.

• Step 5 - Within the for loop, use another for loop to get the total number of set bits (‘1’) in the current mask. Shift j to the left by 1 bit, perform & operation with I, and determine whether the j-th bit is set.

• Step 6 - If the current bit is a set bit, increase the value of the "setBitCount" variable and push "*" into the sequence vector; otherwise, push " " into the sequence vector middle.

• Step 7 - If the value of setBitCount is equal to the value of totalMul, it means we can use the current mask to schedule arithmetic operations; otherwise, we will enter the next iteration.

• Step 8 - In the if statement, define a "currentQueue" using the "deque" data structure to store the array elements.

• Step 9 - Traverse the 'order' list. If the current character is '*', pop the last element in the queue and multiply it with the element at the current array index.

• Step 10 - If the current character in the "orders" list is " ", push the current array element into "currentQueue".

• Step 11 - Use a while loop to pop all elements from "currentQueue" and sum all elements.

• Step 12 - Use the min() function to get the minimum value from the "minimum" and "sum" variables.

Example

#include <bits/stdc++.h>
using namespace std;

// Function to get the minimum number by applying mathematical operations in any order.
int getMinimumSum(int array[], int len, string str){
   // to store a total number of multiplication operators in the string.
   int totalMul = 0;
   for (int i = 0; i < (int)str.size(); i++){
      // increment totalMul if the current character is '*'
      if (str[i] == '*')
         totalMul += 1;
      }
   // store maximum number value in the result.
   int minimum = 1000000;
   // Iterate over all the possible masks and find the minimum value by applying arithmetic operations.
   for (int i = 0; i < (1 << (len - 1)); i++){
      // to store the number of bits set in the mask.
      int setBitCount = 0;
      // to store the order of the operators.
      vector<char> order;
      // finding a total number of mask bits in the current mask 'i'. If the current bit is set to bit, push '*' in the order vector; else, push '+'.
      for (int j = 0; j < len - 1; j++){
         if ((1 << j) & (i)){
            setBitCount += 1;
            order.push_back('*');
         } else {
            order.push_back('+');
         }
      }
      // if the set bit count is equal to the total number of multiplication operators, then only apply the operations.
      if (setBitCount == totalMul){
         // queue to store the current elements.
         deque<int> currentQueue;
         // push the first element in the queue.
         currentQueue.push_back(array[0]);
         for (int j = 0; j < len - 1; j++) {
            // get the current operator from the order vector.
            if (order[j] == '*'){
               // if the current operator is '*', multiply the last element in the queue with the next element in the array.
               int temp = currentQueue.back();
               currentQueue.pop_back();
               temp = temp * array[j + 1];
               // push a new value
               currentQueue.push_back(temp);
            } else {
               // if current operator is '+', then push the next element in the array in the queue.
               currentQueue.push_back(array[j + 1]);
            }
         }
         int sum = 0;
         // Add all the elements in the queue.
         while (currentQueue.size() > 0){
            int temp = currentQueue.front();
            sum += temp;
            currentQueue.pop_front();
         }
         // get the minimum value.
         minimum = min(minimum, sum);
      }
   }
   return minimum;
}

int main(){
   int array[] = {1, 3, 5, 6};
   string str = "*++";
   int len = sizeof(array) / sizeof(array[0]);
   cout << "Minimum number value can be achieved is : " << getMinimumSum(array, len, str);
   return 0;
}

Output

Minimum number value can be achieved is : 14

• Time Complexity - O(2N-1*N), where N is the length of the array. When we iterate over all the bit masks, where we use a for loop to count the total number of set bits in the current mask, it is O(2N-1*N).

• Space complexity − O(N) because we use a list to store the order of arithmetic operators.

The above is the detailed content of The smallest number that can be obtained by applying the "+" and "*" operations to the array elements. For more information, please follow other related articles on the PHP Chinese website!