Rely of Ok-length subarray with every factor lower than X occasions the following one

Given an array A[] of size N and two integers X and Ok, The duty is to rely the variety of indices i (0 ≤ i < N−okay) such that:
X⁰⋅a_i < X¹⋅a_{i + 1} < X²⋅a_i+2 < . . . < X^okay⋅a_i+okay.

Examples:

Enter: A[] = {9, 5, 3, 4, 1}, X = 4, Ok = 1.
Output: 3.
Clarification: Three Subarrays fulfill the situations:
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] however 1.4 = 4.1, so this subarray doesn’t fulfill the situation.

Enter: A[] = {22, 12, 16, 4, 3, 22, 12}, X = 2, Ok = 3.
Output: 1
Clarification: There are whole 4 subarray out of which 1 fulfill the given situation.
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 fulfill the situation.
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 fulfill the situation.
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 fulfill the situation.
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 situation.

Naive Method: To unravel the issue observe the under thought.

Discover all of the subarray of size Ok+1 and such that each factor within the subarray is X occasions smaller than its subsequent factor within the subarray .

Observe the steps under to implement the thought:

• Run a for loop from i = 0 to i < N-(Ok+1). In every iteration:
  • Run a for loop from i to i+Ok and hint that each factor on this subarray is X occasions smaller than the following factor.
  • After termination of the loop if each factor on this loop is X occasions smaller then the following factor increment ans variable by 1.
• Print the reply.

 Beneath is the implementation for the above strategy:

Time complexity: O(N * Ok)
Auxiliary House: O(1).

Environment friendly Method: To unravel the issue observe the under thought.

Utilizing two pointer strategy and checking if each factor within the subarray is 4 occasions smaller then its subsequent factor after which shifting the window ahead until the final factor is reached.

Observe the steps under to implement the thought:

• Run some time loop from j = 0 to j < N – 1. In every iteration:
  • Verify if the the size size of window is the same as Ok + 1 (i.e j – i + 1 = okay + 1) then increment reply by 1.
  • If j^th factor is lower than X occasions (j + 1)^th factor (A[j] < X*A[j + 1]) then increment j by 1 in any other case transfer i pointer to j since no subarray that accommodates j^th and (j+1)^th factor collectively can fulfill the given situation.
• Print the reply.

Beneath is the implementation for the above strategy:

Time Complexity: O(N)
Auxiliary House: O(1)