Подсчет подмассива K-длины, в котором каждый элемент меньше следующего в X раз.

Учитывая массив A[] длины N и два целых числа X и K , задача состоит в том, чтобы подсчитать количество индексов i (0 ≤ i < N−k), таких что:
Икс ⁰ ⋅а _я < Икс ¹ ⋅а _{я + 1} < Икс ² ⋅а _я+2 < . . . < X ^k ⋅a _i+k.

Примеры:

Input: A[] = {9, 5, 3, 4, 1}, X = 4, K = 1.
Output: 3.
Explanation: Three Subarrays satisfy the conditions:
i = 0: the subarray [a0, a1] = [9, 5] and 1.9 < 4.5.
i = 1: the subarray [a1, a2] = [5, 3] and 1.5 < 4.3.
i = 2: the subarray [a2, a3] = [3, 2] and 1.3 < 4.4.
i = 3: the subarray [a3, a4] = [2, 1] but 1.4 = 4.1, so this subarray doesn’t satisfy the condition.

Input: A[] = {22, 12, 16, 4, 3, 22, 12}, X = 2, K = 3.
Output: 1
Explanation: There are total 4 subarray out of which 1 satisfy the given condition.
i = 0: the subarray [a0, a1, a2, a3] = [22, 12, 16, 4] and 1.22 < 2.12 < 4.16 > 8.4, so this subarray doesn’t satisfy the condition.
i = 1: the subarray [a1, a2, a3, a4]=[12, 16, 4, 3] and 1.12 < 2.16 > 4.4 < 8.3, so this subarray doesn’t satisfy the condition.
i = 2: the subarray [a2, a3, a4, a5]=[16, 4, 3, 22] and 1.16 > 2.4 < 4.8 < 8.22, so this subarray doesn’t satisfy the condition.
i = 3: the subarray [a3, a4, a5, a6]=[4, 3, 22, 12] and 1.4 < 2.3 < 4.22 < 8.12, so this subarray satisfies the condition.

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

Find all the subarray of length K+1 and such that every element in the subarray is X times smaller than its next element in the subarray .

Для реализации идеи выполните следующие шаги:

• Запустите цикл for от i = 0 до i < N-(K+1). В каждой итерации:
  • Запустите цикл for от i до i+K и проследите, чтобы каждый элемент в этом подмассиве был в X раз меньше, чем следующий элемент.
  • После завершения цикла, если каждый элемент в этом цикле в Х раз меньше, то следующий элемент увеличивает переменную на 1.
• Распечатайте ответ.

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

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

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

Using two pointer approach and checking if every element in the subarray is 4 times smaller then its next element and then moving the window forward till the last element is reached.

Для реализации идеи выполните следующие шаги:

• Запустите цикл while от j = 0 до j < N – 1 . В каждой итерации:
  • Проверьте, равна ли длина длины окна K + 1 (т.е. j – i + 1 = k + 1), затем увеличьте ответ на 1 .
  • Если j ^-й элемент меньше, чем X раз (j + 1) ^-й элемент (A[j] < X*A[j + 1]), то увеличить j на 1, в противном случае переместите i -й указатель на j , так как нет подмассива, содержащего j ^-й и (j+1) ^-й элемент вместе может удовлетворять заданному условию.
• Распечатайте ответ.

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

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