Thursday, July 7, 2022
HomeWordPress DevelopmentRely of Ok-length subarray with every factor lower than X occasions the...

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:
X0⋅ai < X1⋅ai + 1 < X2⋅ai+2 < . . . < Xokay⋅ai+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:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int resolve(int a[], int n, int okay, int X)

{

    int ans = 0;

    for (int i = 0; i < n - (okay + 1); i++) {

        bool flag = true;

        for (int j = i; j < okay; j++) {

            if (a[j] < X * a[j + 1])

                proceed;

            else {

                flag = false;

            }

        }

        if (flag)

            ans++;

    }

    return ans;

}

  

int principal()

{

    int A[] = { 9, 5, 3, 4, 1 };

    int N = sizeof(A) / sizeof(A[0]);

    int Ok = 1, X = 4;

  

    

    cout << resolve(A, N, Ok, X);

    return 0;

}

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 jth 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 jth and (j+1)th factor collectively can fulfill the given situation.
  • Print the reply.

Beneath is the implementation for the above strategy:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int resolve(int a[], int n, int okay, int X)

{

    int ans = 0;

    int i = 0, j = 0;

  

    

    whereas (j < n - 1) {

        if (j - i + 1 == okay + 1) {

            i++;

            ans++;

        }

        if (a[j] < a[j + 1] * X) {

            j++;

        }

        else {

            i = j;

            j++;

        }

    }

    return ans;

}

  

int principal()

{

    int A[] = { 9, 5, 3, 4, 1 };

    int N = sizeof(A) / sizeof(A[0]);

    int Ok = 1, X = 4;

  

    

    cout << resolve(A, N, Ok, X);

    return 0;

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments