Максимальное количество смежных подмассивов, имеющих GCD X

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

Дан массив arr[] длины N , состоящий из положительных целых чисел и целого числа X, задача состоит в том, чтобы найти максимальное количество смежных подмассивов, выполнив все заданные условия:

  • Каждый подмассив должен иметь GCD, равный X.
  • Один элемент может быть частью только одного подмассива.

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

Примеры:

Input: N = 6, arr[] =  {5, 10, 1, 5, 10, 5}, X = 5
Output: 2
Explanation: 2 Sub-Arrays are possible from index 3 to 3 
and 4 to 5 which are {5} and {10, 5} respectively. 
They both are adjacent to each other as well as there is no element 
in both the Sub-arrays that is a part of both Sub-arrays.
So the maximum number of subarrays is 2.

Input: N = 4, arr[] =  {1, 4, 3, 1}, X = 1
Output: 3
Explanation: The three subarrays are {1}, {4, 3}, {1}

Input: N = 2, arr[] = {5, 10}, X = 5
Output: 1
Explanation: Only one subarray has GCD 5. i.e., {5}.
Notice {5, 10} subarray also has GCD 5 but it cannot be counted because 
then 5 will become part of two subarrays.

Подход: Чтобы решить проблему, следуйте следующей идее:

Problem can be solved by finding all windows in arr[] such that all elements of a window is perfectly divisible by X. Traverse on each window and calculate GCD in a variable let’s say current_gcd . If current_gcd is equal to X then increment counter and set current_gcd = 0.Print the Maximum number of adjacent Sub-Arrays after applying approach on each window.

Иллюстрация подхода:

Consider an example N = 6, arr[] =  {2, 18, 2, 5, 1, 2} and X = 2

Explanation with approach:

All possible continuous windows such that each element of windows is divided by X 

There are Two possible windows that are shown in the picture for start and ending indexes as (0, 2) and (5, 5) respectively. Let’s apply the approach on both of them for Finding Maximum Sub-Arrays satisfying conditions:

In Window1 from index 0 to 2:

Create a counter variable and initialize it to zero, Traverse on window and calculate GCD in variable, let’s say current_gcd.

  • Till index 0, current_gcd= 2, which is equal to X, Hence increment counter to 1 and set current_gcd to 0.
  • Till index 1, current_gcd = 18 , which is not equal to X, Hence counter and current_gcd remains same.
  • Till index 2, current_gcd= 2, which is equal to X, hence increment counter to 2 and set current_gcd to 0

Maximum number of Sub-arrays satisfying given conditions are 2 for this window, Which are {2} and {18, 2}, Both are adjacent and have GCD = 2 along with no same indexed element belongs to Both Sub-Arrays.

In Window 2 from index 5 to 5:

  • There is only one element in the array which is 2, Hence only 1 Sub-Array possible which is {2}.
  • Therefore, Maximum number of Sub-Arrays are = 1.

Maximum possible adjacent Sub-Arrays among all windows is =  2.   

Следуйте инструкциям, чтобы решить проблему:

  • Найдите все окна, каждый элемент которых полностью делится на X.
  • Найдите все начальные и конечные индексы окон и сохраните их в двух списках, скажем, start и end создайте переменную max для хранения максимального количества смежных подмассивов.
  • Перейдите по каждому окну, найдя начальный и конечный индексы всех окон, сохраненных в двух списках на предыдущем шаге, и выполните следующие шаги для каждого окна:
    • Создайте переменную current_gcd и инициализируйте ее нулем .
    • Вычислите GCD при обходе окна и обновите значение current_gcd .
    • Если current_gcd равен X, то увеличиваем счетчик и устанавливаем current_gcd равным 0 .
    • После обхода всего окна обновите max , если счетчик больше max .
  • Выведите значение макс .

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

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

  • Получение всех начальных и конечных индексов окна занимает O (N), а максимальный размер окна может быть равен всему массиву.
  • В этом случае мы можем получить все соседние подмассивы одним обходом массива, поэтому сложность будет O(N).

Вспомогательное пространство: O(N), поскольку начальный и конечный массивы-списки используются для хранения индексов всех окон.

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