Die kleinste Zahl, die durch Anwenden der Operationen „+“ und „*“ auf die Array-Elemente erhalten werden kann

Problemstellung

Wir erhalten ein Array der Länge „N“, das einige positive ganze Zahlen enthält. Zusätzlich erhalten wir eine Zeichenfolge der Länge „N-1“, die nur die Zeichen „*“ und „+“ enthält, wobei „*“ der Multiplikationsoperator und „+“ der Additionsoperator ist. Wir werden aufgefordert, eine arithmetische Operation an den Array-Elementen durchzuführen, um den kleinsten positiven ganzzahligen Wert zu erhalten.

Beispiel

Eintreten

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

Ausgabe

5

Anleitung

Es ist der Ergebniswert von ((1*2) + 3).

Eintreten

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

Ausgabe

15

Anleitung

Es führt array[0]*array[1] aus, was gleich 9 ist und das Ergebnis 1 darstellt. Danach fügt es result1 zu Array[2] hinzu, entspricht 12 und stellt es als result2 dar. Als nächstes fügt es result2 zum Array [3] hinzu, gleich 15.

Eintreten

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

Ausgabe

21

Anleitung

Es ist der Ergebniswert von ((1*3*5) + 6).

Methode 1

Wir werden Bitmaskierung verwenden, um das Problem bei dieser Methode zu lösen.

Immer wenn wir zwei Möglichkeiten haben, können wir Bitmasken verwenden. Hier möchten wir arithmetische Operationen in beliebiger Reihenfolge anwenden, müssen jedoch zwischen Multiplikation und arithmetischen Operationen für eine bestimmte Zeichenfolge wählen

Bitmasken ermöglichen es uns also, alle möglichen Möglichkeiten zur Anordnung zweier arithmetischer Operatoren zu erhalten. Anschließend können wir auf jedem Weg arithmetische Operationen durchführen und prüfen, ob das Ergebnis dem Mindestwert entspricht.

Lassen Sie uns die obige Logik anhand einer Beispieleingabe verdeutlichen. Im folgenden Beispiel ist Array = [1. 3, 5, 6], String = „**++“.

Hier beträgt die Stringlänge 3. Daher können wir insgesamt 8 (2^3) Bitmasken haben, nämlich 000, 001, 010, 100, 110, 101, 011, 111.

Wenn wir nun davon ausgehen, dass „1“ der Operator „*“ und „0“ der Operator „+“ ist, können wir alle Permutationen der in der Zeichenfolge angegebenen arithmetischen Operatoren erhalten.

Allerdings sollten wir eine Permutation nur verwenden, wenn die Gesamtzahl der „1“-Werte gleich der Anzahl der „*“-Operatoren ist und die Anzahl der „0“-Werte gleich der Anzahl der „+“-Operatoren ist.

Algorithmus

Benutzer sollten den folgenden Algorithmus befolgen, um die obige Methode zu implementieren.

• Schritt 1 – Definieren Sie die Variable „totalMul“ und initialisieren Sie sie auf Null, um die Gesamtzahl der multiplikativen arithmetischen Operatoren in der Zeichenfolge zu speichern.

• Schritt 2 – Iterieren Sie mit einer for-Schleife über die angegebene Zeichenfolge. Wenn das aktuelle Zeichen gleich „*“ ist, wird der Wert der Variable „totalMul“ um 1 erhöht.

• Schritt 3 – Verwenden Sie eine for-Schleife, um alle möglichen Bitmasken abzurufen, wenn X gleich der Länge der Zeichenfolge ist. Hier ist „len“ die Array-Länge und „len - 1“ die String-Länge.

• Schritt 4 – Definieren Sie die Variable „setBitCount“, um die Anzahl der in der aktuellen Maske gesetzten Bits zu speichern. Zusätzlich wird eine „Reihenfolge“-Liste definiert, um die aktuelle Reihenfolge der arithmetischen Operationen zu speichern.

• Schritt 5 – Verwenden Sie innerhalb der for-Schleife eine weitere for-Schleife, um die Gesamtzahl der gesetzten Bits („1“) in der aktuellen Maske zu erhalten. Verschieben Sie j um 1 Bit nach links und führen Sie eine Operation mit I durch, um festzustellen, ob das j-te Bit gesetzt ist.

• Schritt 6 – Wenn das aktuelle Bit ein gesetztes Bit ist, erhöhen Sie den Wert der Variablen „setBitCount“ und drücken Sie „*“ in den sequentiellen Vektor; andernfalls drücken Sie „+“ in den sequentiellen Vektor.

• Schritt 7 – Wenn der Wert von setBitCount dem Wert von totalMul entspricht, bedeutet dies, dass wir die arithmetische Operation mit der aktuellen Maske planen können, andernfalls fahren wir mit der nächsten Iteration fort.

• Schritt 8 – Definieren Sie in der if-Anweisung eine „currentQueue“ mithilfe der Datenstruktur „deque“, um die Array-Elemente zu speichern.

• Schritt 9 – Gehen Sie die Bestellliste durch. Wenn das aktuelle Zeichen „*“ ist, fügen Sie das letzte Element in der Warteschlange ein und multiplizieren Sie es mit dem Element am aktuellen Array-Index.

• Schritt 10 – Wenn das aktuelle Zeichen in der Liste „Bestellungen“ „+“ ist, verschieben Sie das aktuelle Array-Element in die „currentQueue“.

• Schritt 11 – Verwenden Sie eine While-Schleife, um alle Elemente aus „currentQueue“ zu entnehmen und alle Elemente zu summieren.

• Schritt 12 – Ermitteln Sie den Mindestwert aus den Variablen „Minimum“ und „Summe“ mithilfe der Funktion min().

Beispiel

#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;
}

Ausgabe

Minimum number value can be achieved is : 14

• Zeitkomplexität – O(2N-1*N), wobei N die Länge des Arrays ist. Wenn wir alle Bitmasken durchlaufen und dabei eine for-Schleife verwenden, um die Gesamtzahl der gesetzten Bits in der aktuellen Maske zu zählen, ist sie O(2N-1*N).

• Raumkomplexität − O(N), weil wir eine Liste verwenden, um die Reihenfolge der arithmetischen Operatoren zu speichern.

Das obige ist der detaillierte Inhalt vonDie kleinste Zahl, die durch Anwenden der Operationen „+“ und „*“ auf die Array-Elemente erhalten werden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!