Минимальное число, которое можно получить, применяя операции «+» и «*» к элементам массива

Опубликовано: 22 Сентября, 2022

Дан массив arr[] , состоящий из N положительных целых чисел, и строка S длины (N – 1) , содержащая символы '+' и '*' , задача состоит в том, чтобы найти наименьшее число, которое можно получить после применения арифметических операций упомянутые в строке S элементы массива в любом порядке.

Примеры:

Input: A[] ={2, 2, 2, 2}, S = “**+”
Output: 8
Explanation:
Operation 1: Perform the multiplication operation on the first two elements operation i.e., arr[0]*arr[1] = 2*2 = 4. Now the array modifies to {4, 2, 2}.
Operation 2: Perform the multiplication operation on the remaining two elements i.e., arr[1]*arr[2] = 2*2 = 4. Now the array modifies to {4, 4}.
Operation 3: Perform the addition operation on the remaining elements arr[0] + arr[1] = 4 + 4 = 8. Now the array modifies to {8}.
Therefore, the result of the operation performed is 8, which is minimum.

Input: A[] = {1, 2, 3, 4}, S = “*++”
Output: 9

Подход: Данную задачу можно решить с помощью битового маскирования. Выполните следующие шаги, чтобы решить проблему:

  • Сохраните количество операций умножения и сложения в строке S в переменных, скажем, mul и add соответственно.
  • Теперь операция, применяемая к элементам массива, может быть закодирована в маске (двоичной строке) таким образом, что если i бит маски установлен, то он равен '1' и должна быть выполнена операция умножения. В противном случае выполните сложение.
  • Инициализируйте переменную, скажем, как INT_MAX , которая хранит минимальное значение результата.
  • Итак, создайте все маски в диапазоне [0, 2 (N – 1) ] и найдите количество установленных битов в маске и выполните следующие шаги:
    • Если количество установленных битов в маске равно mul , то применить эту маску к массиву A[] т.е. если i бит маски равен '1', то выполнить операцию умножения над i элементом и (i + 1) элемент.
    • В противном случае выполните сложение.
    • Обновите значение ans до минимума ans и вычисленного значения на предыдущем шаге.
  • После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 (N – 1) *N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ