Dada una array arr[] de longitud N y un número K , la tarea es contar el número de K-cuentas regresivas en la array.
Se dice que un subarreglo contiguo es una cuenta regresiva K si tiene una longitud K y contiene los números enteros K, K-1, K-2, …, 2, 1 en ese orden. Por ejemplo, [4, 3, 2, 1] es una cuenta regresiva de 4 y [6, 5, 4, 3, 2, 1] es una cuenta regresiva de 6.
Ejemplos:
Entrada: K = 2, arr[] = {3 2 1 2 2 1}
Salida: 2
Explicación: Aquí, K=2 por lo que la array tiene 2 2-Cuenta atrás (2, 1). Una cuenta regresiva es del índice 1 al 2 y la otra es del índice 4 al 5.
Entrada: K = 3, arr[] = {4 3 2 1 5 3 2 1}
Salida: 2
Explicación: Aquí, K=3 entonces el array tiene 2 3-Cuenta atrás (3, 2, 1)
Enfoque: Se recorre la array dada y cada vez que se encuentra el número K, se verifica si todos los números K, K-1, K-2, … hasta 1 están secuencialmente presentes en la array o no. En caso afirmativo, la cuenta aumenta en 1. Si el siguiente número lo saca de la secuencia, se busca la siguiente aparición de K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above program.
#include <bits/stdc++.h>
using namespace std;
// Function to to count the
// number of K-countdowns for
// multiple queries
int countKCountdown(int arr[],
int N,
int K)
{
// flag which stores the
// current value of value
// in the countdown
int flag = -1;
// count of K-countdowns
int count = 0;
// Loop to iterate over the
// elements of the array
for (int i = 0; i < N; i++) {
// condition check if
// the elements
// of the array is
// equal to K
if (arr[i] == K)
flag = K;
// condition check if
// the elements
// of the array is in
// continuous order
if (arr[i] == flag)
flag--;
// condition check if
// the elements
// of the array are not
// in continuous order
else
flag = -1;
// condition check to
// increment the counter
// if the there is a
// K-countdown present
// in the array
if (flag == 0)
count++;
}
// returning the count of
// K-countdowns
return count;
}
// Driver Code
int main()
{
int N = 8;
int K = 3;
int arr[N] = { 4, 3, 2, 1,
5, 3, 2, 1 };
// Function Call
cout << countKCountdown(arr, N, K);
}
Java
// Java code for the above program.
class GFG{
// Function to to count the
// number of K-countdowns for
// multiple queries
public static int countKCountdown(int arr[],
int N, int K)
{
// Flag which stores the
// current value of value
// in the countdown
int flag = -1;
// Count of K-countdowns
int count = 0;
// Loop to iterate over the
// elements of the array
for(int i = 0; i < N; i++)
{
// Condition check if the
// elements of the array is
// equal to K
if (arr[i] == K)
flag = K;
// Condition check if the
// elements of the array is
// in continuous order
if (arr[i] == flag)
flag--;
// Condition check if the
// elements of the array are
// not in continuous order
else
flag = -1;
// Condition check to increment
// the counter if the there is a
// K-countdown present in the array
if (flag == 0)
count++;
}
// Returning the count of
// K-countdowns
return count;
}
// Driver code
public static void main(String[] args)
{
int N = 8;
int K = 3;
int arr[] = { 4, 3, 2, 1, 5, 3, 2, 1 };
System.out.print(countKCountdown(arr, N, K));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 code for the above program. # Function to to count the # number of K-countdowns for # multiple queries def countKCountdown(arr, N, K): # flag which stores the # current value of value # in the countdown flag = -1; # count of K-countdowns count = 0; # Loop to iterate over the # elements of the array for i in range(0, N): # condition check if # the elements # of the array is # equal to K if (arr[i] == K): flag = K; # condition check if # the elements # of the array is in # continuous order if (arr[i] == flag): flag -= 1; # condition check if # the elements # of the array are not # in continuous order else: flag = -1; # condition check to # increment the counter # if the there is a # K-countdown present # in the array if (flag == 0): count += 1; # returning the count of # K-countdowns return count; # Driver Code N = 8; K = 3; arr = [ 4, 3, 2, 1, 5, 3, 2, 1 ]; # Function Call print(countKCountdown(arr, N, K)) # This code is contributed by Akanksha_Rai
C#
// C# code for the above program.
using System;
class GFG{
// Function to to count the
// number of K-countdowns for
// multiple queries
public static int countKCountdown(int []arr,
int N, int K)
{
// Flag which stores the
// current value of value
// in the countdown
int flag = -1;
// Count of K-countdowns
int count = 0;
// Loop to iterate over the
// elements of the array
for(int i = 0; i < N; i++)
{
// Condition check if the
// elements of the array is
// equal to K
if (arr[i] == K)
flag = K;
// Condition check if the
// elements of the array is
// in continuous order
if (arr[i] == flag)
flag--;
// Condition check if the
// elements of the array are
// not in continuous order
else
flag = -1;
// Condition check to increment
// the counter if the there is a
// K-countdown present in the array
if (flag == 0)
count++;
}
// Returning the count of
// K-countdowns
return count;
}
// Driver code
public static void Main()
{
int N = 8;
int K = 3;
int []arr = { 4, 3, 2, 1, 5, 3, 2, 1 };
Console.Write(countKCountdown(arr, N, K));
}
}
// This code is contributed by Akanksha_Rai
Javascript
<script>
//Javascript code for the above program.
// Function to to count the
// number of K-countdowns for
// multiple queries
function countKCountdown( arr, N, K)
{
// flag which stores the
// current value of value
// in the countdown
var flag = -1;
// count of K-countdowns
var count = 0;
// Loop to iterate over the
// elements of the array
for (var i = 0; i < N; i++) {
// condition check if
// the elements
// of the array is
// equal to K
if (arr[i] == K)
flag = K;
// condition check if
// the elements
// of the array is in
// continuous order
if (arr[i] == flag)
flag--;
// condition check if
// the elements
// of the array are not
// in continuous order
else
flag = -1;
// condition check to
// increment the counter
// if the there is a
// K-countdown present
// in the array
if (flag == 0)
count++;
}
// returning the count of
// K-countdowns
return count;
}
var N = 8;
var K = 3;
var arr = [ 4, 3, 2, 1, 5, 3, 2, 1 ];
// Function Call
document.write( countKCountdown(arr, N, K));
// This code is contributed by SoumikMondal
</script>
Producción:
2
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)