Recuento del subarreglo de longitud K con cada elemento menor que X veces el siguiente

Dada una array A[] de longitud N y dos enteros X y K , la tarea es contar el número de índices i (0 ≤ i < N−k) tales que:
X ⁰ ⋅a _i < X ¹ ⋅a _{i + 1} < X ² ⋅a _yo+2 < . . . < X ^k ⋅a _i+k.

Ejemplos:

Entrada: A[] = {9, 5, 3, 4, 1}, X = 4, K = 1.
Salida: 3.
Explicación: tres subarreglos cumplen las condiciones:
i = 0: el subarreglo [a0, a1] = [9, 5] y 1,9 < 4,5.
i = 1: el subarreglo [a1, a2] = [5, 3] y 1.5 < 4.3.
i = 2: el subarreglo [a2, a3] = [3, 2] y 1.3 < 4.4.
i = 3: el subarreglo [a3, a4] = [2, 1] pero 1,4 = 4,1, por lo que este subarreglo no cumple la condición.

Entrada : A[] = {22, 12, 16, 4, 3, 22, 12}, X = 2, K = 3. Salida: 1
Explicación :
Hay un total de 4 subarreglo de los cuales 1 satisface la condición dada.
i = 0: el subarreglo [a0, a1, a2, a3] = [22, 12, 16, 4] y 1,22 < 2,12 < 4,16 > 8,4, por lo que este subarreglo no cumple la condición.
i = 1: el subarreglo [a1, a2, a3, a4]=[12, 16, 4, 3] y 1,12 < 2,16 > 4,4 < 8,3, por lo que este subarreglo no cumple la condición.
i = 2: el subarreglo [a2, a3, a4, a5]=[16, 4, 3, 22] y 1,16 > 2,4 < 4,8 < 8,22, por lo que este subarreglo no cumple la condición.
i = 3: el subarreglo [a3, a4, a5, a6]=[4, 3, 22, 12] y 1.4 < 2.3 < 4.22 < 8.12, entonces este subarreglo satisface la condición.

Enfoque ingenuo: para resolver el problema, siga la siguiente idea.

Encuentre todo el subarreglo de longitud K+1 y tal que cada elemento en el subarreglo sea X veces más pequeño que su siguiente elemento en el subarreglo.

Siga los pasos a continuación para implementar la idea:

• Ejecute un ciclo for desde i = 0 hasta i < N-(K+1). En cada iteración:
  • Ejecute un ciclo for de i a i+K y calcule que cada elemento en este subarreglo es X veces más pequeño que el siguiente elemento.
  • Después de la terminación del ciclo, si cada elemento en este ciclo es X veces más pequeño, el siguiente elemento incrementa la variable en 1.
• Imprime la respuesta.

 A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function performing Calculation
int solve(int a[], int n, int k, int X)
{
    int ans = 0;
    for (int i = 0; i < n - (k + 1); i++) {
        bool flag = true;
        for (int j = i; j < k; j++) {
            if (a[j] < X * a[j + 1])
                continue;
            else {
                flag = false;
            }
        }
        if (flag)
            ans++;
    }
    return ans;
}
 
// Driver Code
int main()
{
    int A[] = { 9, 5, 3, 4, 1 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 1, X = 4;
 
    // Function Call
    cout << solve(A, N, K, X);
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
 
  // Function performing Calculation
  static int solve(int[] a, int n, int k, int X)
  {
    int ans = 0;
    for (int i = 0; i < n - (k + 1); i++) {
      boolean flag = true;
      for (int j = i; j < k; j++) {
        if (a[j] < X * a[j + 1]) {
          continue;
        }
        else {
          flag = false;
        }
      }
      if (flag) {
        ans++;
      }
    }
    return ans;
  }
 
  public static void main(String[] args)
  {
    int[] A = { 9, 5, 3, 4, 1 };
    int N = A.length;
    int K = 1, X = 4;
 
    // Function call
    System.out.print(solve(A, N, K, X));
  }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
// Javascript code to implement the approach
 
// Function performing Calculation
function solve(a, n, k, X)
{
    let ans = 0;
    for (let i = 0; i < n - (k + 1); i++) {
        let flag = true;
        for (let j = i; j < k; j++) {
            if (a[j] < X * a[j + 1])
                continue;
            else {
                flag = false;
            }
        }
        if (flag)
            ans++;
    }
    return ans;
}
 
// Driver Code
    let A = [ 9, 5, 3, 4, 1 ];
    let N = A.length;
    let K = 1, X = 4;
 
    // Function Call
    document.write(solve(A, N, K, X));
     
    // This code is contributed by satwik4409.
    </script>

3

Complejidad temporal : O(N * K)
Espacio auxiliar: O(1).

Enfoque eficiente: para resolver el problema, siga la siguiente idea.

Usando el enfoque de dos punteros y verificando si cada elemento en el subarreglo es 4 veces más pequeño que su siguiente elemento y luego moviendo la ventana hacia adelante hasta que se alcance el último elemento.

Siga los pasos a continuación para implementar la idea:

• Ejecute un ciclo while de j = 0 a j < N – 1 . En cada iteración:
  • Compruebe si la longitud de la ventana es igual a K + 1 (es decir, j – i + 1 = k + 1) y luego incremente la respuesta en 1 .
  • Si j ^th elemento es menor que X veces (j + 1) ^th elemento (A[j] < X*A[j + 1]), entonces incremente j en 1; de lo contrario, mueva el puntero i a j ya que no hay subarreglo que contenga j ^th y (j+1) ^el elemento juntos puede satisfacer la condición dada.
• Imprime la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function performing Calculation
int solve(int a[], int n, int k, int X)
{
    int ans = 0;
    int i = 0, j = 0;
 
    // Loop to utilize the sliding window concept
    while (j < n - 1) {
        if (j - i + 1 == k + 1) {
            i++;
            ans++;
        }
        if (a[j] < a[j + 1] * X) {
            j++;
        }
        else {
            i = j;
            j++;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int A[] = { 9, 5, 3, 4, 1 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 1, X = 4;
 
    // Function Call
    cout << solve(A, N, K, X);
    return 0;
}

# Python code to implement the approach
 
# Function performing Calculation
def solve(a, n, k, X):
    ans = 0
    for i in range(n - (k + 1)):
        flag = True
        for j in range(i, k):
            if a[j] < X * a[j + 1]:
                continue
            else:
                flag = False
        if flag:
            ans += 1
    return ans
 
if __name__ == '__main__':
    A = [9, 5, 3, 4, 1]
    N = len(A)
    K = 1
    X = 4
 
    # Function Call
    print(solve(A, N, K, X))
 
# This code is contributed by Tapesh(tapeshdua420)

<script>
    // JavaScript code to implement the approach
 
    // Function performing Calculation
    const solve = (a, n, k, X) => {
        let ans = 0;
        let i = 0, j = 0;
 
        // Loop to utilize the sliding window concept
        while (j < n - 1) {
            if (j - i + 1 == k + 1) {
                i++;
                ans++;
            }
            if (a[j] < a[j + 1] * X) {
                j++;
            }
            else {
                i = j;
                j++;
            }
        }
        return ans;
    }
 
    // Driver Code
 
    let A = [9, 5, 3, 4, 1];
    let N = A.length;
    let K = 1, X = 4;
 
    // Function Call
    document.write(solve(A, N, K, X));
 
    // This code is contributed by rakeshsahni
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)