Подмассив минимальной длины, начинающийся с каждого индекса с максимальным ИЛИ

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

Дан массив размера N . Рассмотрим все подмассивы, начиная с каждого индекса из [0, N – 1]. Определите длину наименьшего подмассива, начиная с каждого индекса, у которого побитовое ИЛИ является максимальным.

Примеры:

Input: N = 5, A = {1, 2, 3, 4, 5}
Output: {4, 3, 2, 2, 1}
Explanation: 

  • For i = 1, and size of subarray = 1, score of this subarray is 1. 
    For size = 2, the value is 1 | 2 = 3. 
    For size = 3, the value is 1 | 2 | 3 = 3.
    For size = 4, the value is 1 | 2 | 3 | 4 = 7 and 
    for size = 5, the value of this subarray is 1 | 2 | 3 | 4 | 5 = 7. 
    You can see that the maximum value is 7, and the smallest size 
    of the subarray starting at 1 with this value is of size 4. 
    So the maximum answer starting from 1st index is equal to 4.
  • For i = 2 and size = 1, the value is 2. 
    For size = 2, the value is 2 | 3 = 3. 
    For size = 3, the value is 2 | 3 | 4 = 7. 
    For size = 4, the value is 2 | 3 | 4 | 5 = 7. 
    You can see that the maximum score is 7, and the smallest size 
    of the subarray starting at 2, with this value is of size 3. 
    So the maximum answer starting from 2nd index is equal to 3.
  • For i = 3 and size = 1, the value is 3. 
    For size = 2, the value is 3 | 4 = 7. 
    For size = 3, the value is 3 | 4 | 5 = 7. 
    So for i = 3 the size is 2
  • For i = 4 and size = 1, the score is 4 and for size = 2, the score is 4 | 1 = 5. 
    So the size is equal to 2.
  • For i = 5 only one subarray is there of size 1.

Input: N = 7, A = {2, 4, 3, 1, 5, 4, 6}
Output: {3, 2, 3, 4, 3, 2, 1}

Наивный подход: чтобы решить проблему, следуйте следующей идее:

For each index find all the subarrays starting from that index and find the smallest one with maximum bitwise OR.

Выполните указанные шаги, чтобы решить проблему, используя описанный выше подход:

  • Пройдите массив, используя два вложенных цикла for, чтобы найти все возможные подмассивы.
  • Вычислите значение OR для каждого подмассива и обновите максимальный ответ, найденный на данный момент, для текущего начального индекса.
  • Поместите размер подмассива минимальной длины с максимальным значением в массив ответов.
  • Вернуть массив ответов.

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

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

Эффективный подход: для решения проблемы следуйте следующей идее:

By observing the functionality of OR, bits can only be turned on using 1. So, start from the end and keep track of the minimum index that will keep the particular bit as a set and then we take a max of all the indexes that contain the set bits.

Выполните указанные шаги, чтобы решить проблему, используя описанный выше подход:

  • Пройдите по заданному массиву с конца и обновите минимальный индекс каждого установленного бита в текущем элементе.
  • Возьмите максимальный индекс всех установленных битов в качестве ответа для текущего индекса.
  • Вернуть массив ответов

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

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

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