Найдите минимальное количество непалиндромных разделов двоичного массива

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

Учитывая двоичный массив A[] длины 2*N , задача состоит в том, чтобы найти минимальное количество разделов, соответствующих следующим условиям:

  • Каждый элемент массива принадлежит ровно одному разделу
  • Ни один из разделенных подмассивов не является палиндромом

Примечание. Если ответов несколько, выведите любой, удовлетворяющий приведенным выше условиям. и если такого раздела, который удовлетворяет вышеуказанному условию, не существует, выведите -1.

Примеры:

Input: A[] = {1, 0, 1, 1, 0, 1} 
Output: 2

Explanation: One of the valid partitions of A = {1, 0, 1, 1, 0, 1} is {1, 0} and {1, 1, 0, 1} which satisfy above conditions.Hence we can partition an array into 2 subarrays.

Input: A[] = {1, 0, 0, 1, 0, 0, 1, 1}
Output: 1
Explanation: Here A = {1, 0, 0, 1, 0, 0, 1, 1} is itself not a palindrome. Then, no more partitioning needs to be done: just take A itself. Hence number of partitions of an array is 1.

Подход: Задача может быть решена на основе следующего наблюдения:

  • A trivial impossible case is when an array A consists of only 0’s or only 1’s as an element and print -1.
  • In every other case, a valid partition exists and only 2 partitions are sufficient.
    • Suppose A is itself not a palindrome. Then, no more partitioning needs to be done: just take A itself.
    • Now we consider the case when A is a palindrome. Note that the length of A is even.
      • Suppose the first half of A is not a palindrome. Then, its second half is also not a palindrome, so simply partition it into these two halves.
      • Otherwise, the first N elements of A form a palindrome. In this case, consider the string formed by the first N+1 elements of A: this is definitely not a palindrome.

Выполните следующие шаги, чтобы решить проблему:

  • Проверьте, является ли массив палиндромом или нет, и если массив не является палиндромом, выведите 1.
  • После этого проверьте, состоит ли массив A[] только из 0 или только из 1 в качестве элемента, и если это правда, то выведите -1.
  • В противном случае выведите 2 в качестве ответа на количество разделов массива, удовлетворяющих условиям.

Ниже приведена реализация описанного выше подхода.

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

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