Cuente los subarreglos que consisten en los primeros K números naturales en orden descendente

Dada una array arr[] de tamaño N y un número entero K , la tarea es contar el número de subarreglos que consta de los primeros K números naturales en orden descendente.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 7, 9, 3, 2, 1, 8, 3, 2, 1}, K = 3
Salida: 2
Explicación: Aparece el subarreglo {3, 2, 1} dos veces en la array.

Entrada: arr = {100, 7, 6, 5, 4, 3, 2, 1, 100}, K = 6
Salida: 1

Enfoque: la idea es atravesar la array y verificar si la secuencia decreciente requerida está presente a partir del índice actual o no. Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, temp a K , que verifica el patrón, y count con 0 , para almacenar el recuento del subarreglo total coincidente.
• Recorra la array arr[] usando la variable i y haga lo siguiente:
  • Si arr[i] es igual a temp y el valor de temp es 1 , entonces incremente el conteo en 1 y actualice temp como K . De lo contrario, disminuya la temperatura en 1 .
  • De lo contrario, actualice temp como temp = K y si arr[i] es igual a K , disminuya i en 1 .
• Después de los pasos anteriores, imprima el valor de cuenta como resultado.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count subarray having
// the decreasing sequence K to 1
int CountSubarray(int arr[], int n,
                  int k)
{
    int temp = k, count = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // Check if required sequence
        // is present or not
        if (arr[i] == temp) {
            if (temp == 1) {
                count++;
                temp = k;
            }
            else
                temp--;
        }
 
        // Reset temp to k
        else {
            temp = k;
            if (arr[i] == k)
                i--;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 7, 9, 3,
                  2, 1, 8, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    // Function Call
    cout << CountSubarray(arr, N, K);
 
    return 0;
}
 
// This code is contributed by Dharanendra L V

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to count subarray having
  // the decreasing sequence K to 1
  static int CountSubarray(int arr[], int n,
                           int k)
  {
    int temp = k, count = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
      // Check if required sequence
      // is present or not
      if (arr[i] == temp) {
        if (temp == 1) {
          count++;
          temp = k;
        }
        else
          temp--;
      }
 
      // Reset temp to k
      else {
        temp = k;
        if (arr[i] == k)
          i--;
      }
    }
 
    // Return the count
    return count;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = { 1, 2, 3, 7, 9, 3,
                 2, 1, 8, 3, 2, 1 };
    int N = arr.length;
    int K = 3;
 
    // Function Call
    System.out.println(CountSubarray(arr, N, K));
  }
}
 
// This code is contributed by shivanisinghss2110

# Python3 program for the above approach
 
# Function to count subarray having
# the decreasing sequence K to 1
def CountSubarray(arr, n, k):
     
    temp = k
    count = 0
 
    # Traverse the array
    for i in range(n):
 
        # Check if required sequence
        # is present or not
        if (arr[i] == temp):
            if (temp == 1):
                count += 1
                temp = k
            else:
                   temp -= 1
 
        # Reset temp to k
        else:
            temp = k
             
            if (arr[i] == k):
                i -= 1
 
    # Return the count
    return count
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 3, 7, 9, 3,
            2, 1, 8, 3, 2, 1 ]
    N = len(arr)
    K = 3
 
    # Function Call
    print(CountSubarray(arr, N, K))
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count subarray having
// the decreasing sequence K to 1
static int CountSubarray(int[] arr,
                         int n, int k)
{
    int temp = k, count = 0;
 
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
         
        // Check if required sequence
        // is present or not
        if (arr[i] == temp)
        {
            if (temp == 1)
            {
                count++;
                temp = k;
            }
            else
                temp--;
        }
 
        // Reset temp to k
        else
        {
            temp = k;
             
            if (arr[i] == k)
                i--;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver code
static public void Main()
{
    int[] arr = { 1, 2, 3, 7, 9, 3,
                  2, 1, 8, 3, 2, 1 };
    int N = arr.Length;
    int K = 3;
 
    // Function Call
    Console.Write(CountSubarray(arr, N, K));
}
}
 
// This code is contributed by Dharanendra L V

<script>
 
      // JavaScript program for the above approach
 
      // Function to count subarray having
      // the decreasing sequence K to 1
      function CountSubarray(arr, n, k) {
        var temp = k,
          count = 0;
 
        // Traverse the array
        for (var i = 0; i < n; i++)
        {
          // Check if required sequence
          // is present or not
          if (arr[i] == temp)
          {
            if (temp == 1) {
              count++;
              temp = k;
            } else temp--;
          }
 
          // Reset temp to k
          else {
            temp = k;
            if (arr[i] == k) i--;
          }
        }
 
        // Return the count
        return count;
      }
 
      // Driver Code
 
      var arr = [1, 2, 3, 7, 9, 3, 2, 1, 8, 3, 2, 1];
      var N = arr.length;
      var K = 3;
 
      // Function Call
      document.write(CountSubarray(arr, N, K));
       
</script>

2

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