Dados dos enteros M y K y una array arr[] que consta de N enteros positivos, la tarea es verificar si la array se puede dividir en K subarreglos consecutivos que no se superponen de longitud M , de modo que cada subarreglo consta de un solo elemento distinto. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {6, 1, 3, 3, 3, 3}, M = 1, K = 3
Salida: Sí
Explicación:
Los K subarreglos consecutivos que no se superponen son {6}, {1}, {3 , 3, 3, 3}.Entrada: arr[] = {3, 5, 3, 5, 3, 1}, M = 2, K = 3
Salida: No
Enfoque: el problema dado se puede resolver utilizando un recorrido de array simple y verificando si el elemento en el índice actual i y el elemento en el índice (i + M) son iguales o no. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, count y t con 1 y 0 respectivamente, para almacenar el recuento total de patrones coincidentes y la longitud actual del patrón coincidente, respectivamente.
- Recorra la array dada en el rango [0, N – M – 1] usando la variable i y haga lo siguiente:
- Si el valor de arr[i] y arr[i + M] es el mismo, entonces, incremente t en 1 y si t es el mismo que m , actualice t a 0 e incremente el conteo . Si el valor de la cuenta es K , imprima «Sí» y salga del bucle .
- De lo contrario, si t es M , aumente la cuenta en 1 .
- Después de los pasos anteriores, si el valor de la cuenta no es el mismo que K , imprima «No» , ya que no existe tal patrón.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if array can be split
// into K consecutive and non-overlapping
// subarrays of length M consisting of a
// single distinct element
string checkPattern(int arr[], int m,
int k, int n)
{
int count = 1, t = 0;
// Traverse over the range [0, N - M - 1]
for (int i = 0; i < n - m; i++) {
// Check if arr[i] is the
// same as arr[i + m]
if (arr[i] == arr[i + m]) {
// Increment current length
// t of pattern matched by 1
t++;
// Check if t is equal to m,
// increment count of total
// repeated pattern
if (t == m) {
t = 0;
count++;
// Return true if length of
// total repeated pattern is k
if (count == k) {
return "Yes";
}
}
}
else {
// Update length of the
// current pattern
t = 0;
// Update count to 1
count = 1;
}
}
// Finally return false if
// no pattern found
return "No";
}
// Driver Code
int main()
{
int arr[] = { 6, 1, 3, 3, 3, 3 };
int M = 1, K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << checkPattern(arr, M, K, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if array can be split
// into K consecutive and non-overlapping
// subarrays of length M consisting of a
// single distinct element
static String checkPattern(int arr[], int m,
int k, int n)
{
int count = 1, t = 0;
// Traverse over the range [0, N - M - 1]
for (int i = 0; i < n - m; i++)
{
// Check if arr[i] is the
// same as arr[i + m]
if (arr[i] == arr[i + m])
{
// Increment current length
// t of pattern matched by 1
t++;
// Check if t is equal to m,
// increment count of total
// repeated pattern
if (t == m)
{
t = 0;
count++;
// Return true if length of
// total repeated pattern is k
if (count == k)
{
return "Yes";
}
}
}
else
{
// Update length of the
// current pattern
t = 0;
// Update count to 1
count = 1;
}
}
// Finally return false if
// no pattern found
return "No";
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6, 1, 3, 3, 3, 3 };
int M = 1, K = 3;
int N = arr.length;
System.out.print(checkPattern(arr, M, K, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to check if array can be split # into K consecutive and non-overlapping # subarrays of length M consisting of a # single distinct element def checkPattern(arr, m, k, n): count = 1 t = 0 # Traverse over the range [0, N - M - 1] for i in range(n - m): # Check if arr[i] is the # same as arr[i + m] if (arr[i] == arr[i + m]): # Increment current length # t of pattern matched by 1 t += 1 # Check if t is equal to m, # increment count of total # repeated pattern if (t == m): t = 0 count += 1 # Return true if length of # total repeated pattern is k if (count == k): return "Yes" else: # Update length of the # current pattern t = 0 # Update count to 1 count = 1 # Finally return false if # no pattern found return "No" # Driver Code if __name__ == '__main__': arr = [6, 1, 3, 3, 3, 3] M = 1 K = 3 N = len(arr) print(checkPattern(arr, M, K, N)) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if array can be split
// into K consecutive and non-overlapping
// subarrays of length M consisting of a
// single distinct element
static String checkPattern(int []arr, int m,
int k, int n)
{
int count = 1, t = 0;
// Traverse over the range [0, N - M - 1]
for (int i = 0; i < n - m; i++)
{
// Check if arr[i] is the
// same as arr[i + m]
if (arr[i] == arr[i + m])
{
// Increment current length
// t of pattern matched by 1
t++;
// Check if t is equal to m,
// increment count of total
// repeated pattern
if (t == m)
{
t = 0;
count++;
// Return true if length of
// total repeated pattern is k
if (count == k)
{
return "Yes";
}
}
}
else
{
// Update length of the
// current pattern
t = 0;
// Update count to 1
count = 1;
}
}
// Finally return false if
// no pattern found
return "No";
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 1, 3, 3, 3, 3 };
int M = 1, K = 3;
int N = arr.Length;
Console.Write(checkPattern(arr, M, K, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Js program for the above approach
// Function to check if array can be split
// into K consecutive and non-overlapping
// subarrays of length M consisting of a
// single distinct element
function checkPattern( arr, m, k, n)
{
let count = 1, t = 0;
// Traverse over the range [0, N - M - 1]
for (let i = 0; i < n - m; i++) {
// Check if arr[i] is the
// same as arr[i + m]
if (arr[i] == arr[i + m]) {
// Increment current length
// t of pattern matched by 1
t++;
// Check if t is equal to m,
// increment count of total
// repeated pattern
if (t == m) {
t = 0;
count++;
// Return true if length of
// total repeated pattern is k
if (count == k) {
return "Yes";
}
}
}
else {
// Update length of the
// current pattern
t = 0;
// Update count to 1
count = 1;
}
}
// Finally return false if
// no pattern found
return "No";
}
// Driver Code
let arr = [ 6, 1, 3, 3, 3, 3 ];
let M = 1, K = 3;
let N = arr.length;
document.write( checkPattern(arr, M, K, N));
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RitikBansal2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA