Dado un arreglo arr[] que consta de N enteros y dos enteros positivos M y K , la tarea es verificar si existe algún subarreglo de longitud M que se repita consecutivamente al menos K veces. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {2, 1, 2, 1, 1, 1, 3}, M = 2, K = 2
Salida: Sí
Explicación: El subarreglo {2, 1} de longitud 2 repite al menos K(= 2) veces consecutivas.Entrada: arr[] = {7, 1, 3, 1, 1, 1, 1, 3}, M = 1, K = 3
Salida: Sí
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de longitud M y verificar para cada subarreglo, si al concatenarlo exactamente K veces está presente como un subarreglo en el arreglo dado o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to check if there exists
// any subarray of length M repeating
// at least K times consecutively
bool check(int arr[], int M, int K,
int ind)
{
// Iterate from i equal 0 to M
for (int i = 0; i < M; i++) {
// Iterate from j equals 1 to K
for (int j = 1; j < K; j++) {
// If elements at pos + i and
// pos + i + j * M are not equal
if (arr[ind + i]
!= arr[ind + i + j * M]) {
return false;
}
}
}
return true;
}
// Function to check if a subarray repeats
// at least K times consecutively or not
bool SubarrayRepeatsKorMore(
int arr[], int N, int M, int K)
{
// Iterate from ind equal 0 to M
for (int ind = 0;
ind <= N - M * K; ind++) {
// Check if subarray arr[i, i + M]
// repeats atleast K times or not
if (check(arr, M, K, ind)) {
return true;
}
}
// Otherwise, return false
return false;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 2, 1, 1, 1, 3 };
int M = 2, K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
if (SubarrayRepeatsKorMore(
arr, N, M, K)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if there exists
// any subarray of length M repeating
// at least K times consecutively
static boolean check(int arr[], int M,
int K, int ind)
{
// Iterate from i equal 0 to M
for(int i = 0; i < M; i++)
{
// Iterate from j equals 1 to K
for(int j = 1; j < K; j++)
{
// If elements at pos + i and
// pos + i + j * M are not equal
if (arr[ind + i] != arr[ind + i + j * M])
{
return false;
}
}
}
return true;
}
// Function to check if a subarray repeats
// at least K times consecutively or not
static boolean SubarrayRepeatsKorMore(int arr[], int N,
int M, int K)
{
// Iterate from ind equal 0 to M
for(int ind = 0; ind <= N - M * K; ind++)
{
// Check if subarray arr[i, i + M]
// repeats atleast K times or not
if (check(arr, M, K, ind))
{
return true;
}
}
// Otherwise, return false
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 1, 2, 1, 1, 1, 3 };
int M = 2, K = 2;
int N = arr.length;
if (SubarrayRepeatsKorMore(arr, N, M, K))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to check if there exists
# any subarray of length M repeating
# at least K times consecutively
def check(arr, M, K, ind):
# Iterate from i equal 0 to M
for i in range(M):
# Iterate from j equals 1 to K
for j in range(1, K, 1):
# If elements at pos + i and
# pos + i + j * M are not equal
if (arr[ind + i] != arr[ind + i + j * M]):
return False
return True
# Function to check if a subarray repeats
# at least K times consecutively or not
def SubarrayRepeatsKorMore(arr, N, M, K):
# Iterate from ind equal 0 to M
for ind in range(N - M * K + 1):
# Check if subarray arr[i, i + M]
# repeats atleast K times or not
if (check(arr, M, K, ind)):
return True
# Otherwise, return false
return False
# Driver Code
if __name__ == '__main__':
arr = [2, 1, 2, 1, 1, 1, 3]
M = 2
K = 2
N = len(arr)
if (SubarrayRepeatsKorMore(arr, N, M, K)):
print("Yes")
else:
print("No")
# This code is contributed by bgangwar59
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if there exists
// any subarray of length M repeating
// at least K times consecutively
static bool check(int[] arr, int M, int K,
int ind)
{
// Iterate from i equal 0 to M
for(int i = 0; i < M; i++)
{
// Iterate from j equals 1 to K
for(int j = 1; j < K; j++)
{
// If elements at pos + i and
// pos + i + j * M are not equal
if (arr[ind + i] != arr[ind + i + j * M])
{
return false;
}
}
}
return true;
}
// Function to check if a subarray repeats
// at least K times consecutively or not
static bool SubarrayRepeatsKorMore(int[] arr, int N,
int M, int K)
{
// Iterate from ind equal 0 to M
for(int ind = 0; ind <= N - M * K; ind++)
{
// Check if subarray arr[i, i + M]
// repeats atleast K times or not
if (check(arr, M, K, ind))
{
return true;
}
}
// Otherwise, return false
return false;
}
// Driver code
static void Main()
{
int[] arr = { 2, 1, 2, 1, 1, 1, 3 };
int M = 2, K = 2;
int N = arr.Length;
if (SubarrayRepeatsKorMore(
arr, N, M, K))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to check if there exists
// any subarray of length M repeating
// at least K times consecutively
function check(arr, M, K, ind)
{
// Iterate from i equal 0 to M
for(let i = 0; i < M; i++)
{
// Iterate from j equals 1 to K
for(let j = 1; j < K; j++)
{
// If elements at pos + i and
// pos + i + j * M are not equal
if (arr[ind + i] !=
arr[ind + i + j * M])
{
return false;
}
}
}
return true;
}
// Function to check if a subarray repeats
// at least K times consecutively or not
function SubarrayRepeatsKorMore(arr, N, M, K)
{
// Iterate from ind equal 0 to M
for(let ind = 0;
ind <= N - M * K; ind++)
{
// Check if subarray arr[i, i + M]
// repeats atleast K times or not
if (check(arr, M, K, ind))
{
return true;
}
}
// Otherwise, return false
return false;
}
// Driver Code
let arr = [ 2, 1, 2, 1, 1, 1, 3 ];
let M = 2, K = 2;
let N = arr.length;
if (SubarrayRepeatsKorMore(arr, N, M, K))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by subhammahato348
</script>
Producción:
Yes
Complejidad temporal: O(N*M*K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la técnica de dos punteros . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 .
- Recorra la array dada arr[] sobre el rango de índices [0, N – M] usando una variable, digamos i , y realice los siguientes pasos:
- Si el valor de arr[i] es igual a arr[i + M] , entonces incremente el conteo en 1 , ya que hay una coincidencia en el subarreglo.
- De lo contrario, actualice el recuento a 0 cuando haya una ruptura en los subarreglos contiguos.
- Si el valor de count es M * (K – 1) , entonces significa que hay K subarreglos consecutivamente iguales de longitud M. Por lo tanto, imprima «Sí» y salga del bucle .
- Después de completar los pasos anteriores, si el conteo nunca llega a ser M * (K – 1) , imprima “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to check if any subarray
// of length M repeats at least
// K times consecutively or not
bool checkExists(int arr[], int N,
int M, int K)
{
// Stores the required count
// of repeated subarrays
int count = 0;
for (int i = 0; i < N - M; i++) {
// Check if the next continuous
// subarray has equal elements
if (arr[i] == arr[i + M])
count++;
else
count = 0;
// Check if K continuous subarray
// of length M are found or not
if (count == M * (K - 1))
return true;
}
// If no subarrays are found
return false;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 2, 1, 1, 1, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 2, K = 2;
if (checkExists(arr, N, M, K)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if any subarray
// of length M repeats at least
// K times consecutively or not
static boolean checkExists(int arr[], int N,
int M, int K)
{
// Stores the required count
// of repeated subarrays
int count = 0;
for(int i = 0; i < N - M; i++)
{
// Check if the next continuous
// subarray has equal elements
if (arr[i] == arr[i + M])
count++;
else
count = 0;
// Check if K continuous subarray
// of length M are found or not
if (count == M * (K - 1))
return true;
}
// If no subarrays are found
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 1, 2, 1, 1, 1, 3 };
int M = 2, K = 2;
int N = arr.length;
if (checkExists(arr, N, M, K))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to check if any subarray
# of length M repeats at least
# K times consecutively or not
def checkExists(arr, N, M, K):
# Stores the required count
# of repeated subarrays
count = 0
for i in range(N - M):
# Check if the next continuous
# subarray has equal elements
if (arr[i] == arr[i + M]):
count += 1
else:
count = 0
# Check if K continuous subarray
# of length M are found or not
if (count == M * (K - 1)):
return True
# If no subarrays are found
return False
# Driver Code
if __name__ == '__main__':
arr = [ 2, 1, 2, 1, 1, 1, 3 ]
N = len(arr)
M = 2
K = 2
if (checkExists(arr, N, M, K)):
print("Yes")
else:
print("No")
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if any subarray
// of length M repeats at least
// K times consecutively or not
public static bool checkExists(int []arr, int N,
int M, int K)
{
// Stores the required count
// of repeated subarrays
int count = 0;
for(int i = 0; i < N - M; i++)
{
// Check if the next continuous
// subarray has equal elements
if (arr[i] == arr[i + M])
count++;
else
count = 0;
// Check if K continuous subarray
// of length M are found or not
if (count == M * (K - 1))
return true;
}
// If no subarrays are found
return false;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 1, 2, 1, 1, 1, 3 };
int N = arr.Length;
int M = 2, K = 2;
if (checkExists(arr, N, M, K))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program for the above approach
// Function to check if any subarray
// of length M repeats at least
// K times consecutively or not
function checkExists(arr, N, M, K)
{
// Stores the required count
// of repeated subarrays
let count = 0;
for (let i = 0; i < N - M; i++) {
// Check if the next continuous
// subarray has equal elements
if (arr[i] == arr[i + M])
count++;
else
count = 0;
// Check if K continuous subarray
// of length M are found or not
if (count == M * (K - 1))
return true;
}
// If no subarrays are found
return false;
}
// Driver Code
let arr = [ 2, 1, 2, 1, 1, 1, 3 ];
let N = arr.length;
let M = 2, K = 2;
if (checkExists(arr, N, M, K)) {
document.write("Yes");
}
else {
document.write("No");
}
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array