Максимизируйте значение двоичной строки, заменив элементы A[i]th с начала или с конца

Опубликовано: 27 Февраля, 2023

Дана строка S размера M , состоящая только из нулей (и, следовательно, представляющая целое число 0). Кроме того, дан массив A[] размера N , каждый элемент которого является целым числом в диапазоне [1, M] . Задача состоит в том, чтобы максимизировать целое число, представленное строкой, выполнив следующую операцию N раз:

  • В i -й (1 ≤ i ≤ N) операции замените либо A[i] -й термин, либо (M+1-A[i]) -й термин на 1.
  • Символы в одной и той же позиции могут быть изменены более одного раза.

Примеры :

Input: N = 4, M = 5, S = “00000”, A = {1, 1, 3, 1}
Output: “10101”
Explanation: In 1st operation, the element at 1st position (0-th index) 
is transformed into 1. 
In 2nd operation, since element at 1st position is already 1,  
so make element at 5th position equal to 1. 
In 3rd operation, make element at 3rd position equal to 1. 
In 4th operation, we can make either element at 1st 
or 5th position equal to 1. Both of them are already 1.

Input : N=1, M=5, S=”00000″, A={2}
Output : “01000”

Подход :

The problem can be solved easily by a greedy approach. The catch here is that to maximize the integer represented by the string, we must try to convert the 0s to 1s which are on as left as possible i.e., nearest to the most significant bit.

Для решения этой проблемы можно предпринять следующие шаги:

  • Перебрать элементы A[] .
    • Для удобства сделаем A[i] = min(A[i], M+1-A[i]).
    • Чтобы обработать 0-индексацию массива, M-1-A[i] будет записано вместо M+1-A[i].
    • Если A[i] -й символ S не равен 1, мы заменим его.
    • В противном случае мы заменим (M+1-A[i]) -й символ.
  • Верните окончательную строку в качестве требуемого ответа.

Ниже приведен код, основанный на вышеуказанном подходе:

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

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