Dado un arreglo arr[] de N enteros, la tarea es encontrar el subarreglo más pequeño brr [] de tamaño al menos 2 tal que al realizar la operación repetitiva en el arreglo brr[] da el arreglo original arr[] . Imprima «-1» si no es posible encontrar dicho subarreglo.
Una operación repetitiva en una array es agregar todo el elemento actual de la array a la misma array nuevamente.
Por ejemplo , si una array arr[] = {1, 2} , al repetir la operación, la array se convierte en {1, 2, 1, 2} .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 3, 1, 2, 3, 3}
Salida: {1, 2, 3, 3}
Explicación:
{1, 2, 3, 3} es el subarreglo más pequeño que cuando se repite 2 veces da la array original {1, 2, 3, 3, 1, 2, 3, 3}Entrada: arr[] = {1, 1, 6, 1, 1, 7}
Salida: -1
Explicación:
No existe ningún subarreglo.
Enfoque ingenuo: la idea es generar todos los subarreglos posibles de longitud de al menos 2 y verificar si la repetición de esos subarreglos da como resultado el arreglo original o no.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar observando el hecho de que el subarreglo resultante brr[] debe comenzar desde el primer índice del arreglo original para generar arr[] en repetición. Por lo tanto, genere solo aquellos subarreglos que comiencen desde el primer índice y tengan una longitud de al menos 2 y verifique si la repetición de esos subarreglos da como resultado el arreglo original o no. A continuación se muestran los pasos:
- Cree una array auxiliar brr[] e inserte los dos primeros elementos de la array original en ella, ya que la array resultante debe tener al menos dos de tamaño.
- Recorra la longitud posible del subarreglo [2, N/2 + 1] y verifique si el arreglo brr[] de longitud i al repetirlo da el arreglo original arr[] o no.
- En caso afirmativo, imprima este subarreglo y rompa el ciclo.
- De lo contrario, inserte el elemento actual en el subarreglo y verifique nuevamente.
- Repita los pasos anteriores hasta que se comprueben todos los subarreglos.
- Imprima «-1» si no se encuentra la array brr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <vector>
using namespace std;
// Function to print the array
void printArray(vector<int>& brr)
{
for (auto& it : brr) {
cout << it << ' ';
}
}
// Function to find the smallest subarray
void RepeatingSubarray(int arr[], int N)
{
// Corner Case
if (N < 2) {
cout << "-1";
}
// Initialize the auxiliary subarray
vector<int> brr;
// Push the first 2 elements into
// the subarray brr[]
brr.push_back(arr[0]);
brr.push_back(arr[1]);
// Iterate over the length of
// subarray
for (int i = 2; i < N / 2 + 1; i++) {
// If array can be divided into
// subarray of i equal length
if (N % i == 0) {
bool a = false;
int n = brr.size();
int j = i;
// Check if on repeating the
// current subarray gives the
// original array or not
while (j < N) {
int K = j % i;
if (arr[j] == brr[K]) {
j++;
}
else {
a = true;
break;
}
}
// Subarray found
if (!a && j == N) {
printArray(brr);
return;
}
}
// Add current element into
// subarray
brr.push_back(arr[i]);
}
// No subarray found
cout << "-1";
return;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 1, 2,
2, 1, 2, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
RepeatingSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the array
static void printArray(Vector<Integer> brr)
{
for(int it : brr)
{
System.out.print(it + " ");
}
}
// Function to find the smallest subarray
static void RepeatingSubarray(int arr[], int N)
{
// Corner Case
if (N < 2)
{
System.out.print("-1");
}
// Initialize the auxiliary subarray
Vector<Integer> brr = new Vector<Integer>();
// Push the first 2 elements into
// the subarray brr[]
brr.add(arr[0]);
brr.add(arr[1]);
// Iterate over the length of
// subarray
for(int i = 2; i < N / 2 + 1; i++)
{
// If array can be divided into
// subarray of i equal length
if (N % i == 0)
{
boolean a = false;
int n = brr.size();
int j = i;
// Check if on repeating the
// current subarray gives the
// original array or not
while (j < N)
{
int K = j % i;
if (arr[j] == brr.get(K))
{
j++;
}
else
{
a = true;
break;
}
}
// Subarray found
if (!a && j == N)
{
printArray(brr);
return;
}
}
// Add current element into
// subarray
brr.add(arr[i]);
}
// No subarray found
System.out.print("-1");
return;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 1, 2,
2, 1, 2, 2 };
int N = arr.length;
// Function call
RepeatingSubarray(arr, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to print the array
def printArray(brr):
for it in brr:
print(it, end = ' ')
# Function to find the smallest subarray
def RepeatingSubarray(arr, N):
# Corner Case
if (N < 2):
print("-1")
# Initialize the auxiliary subarray
brr = []
# Push the first 2 elements into
# the subarray brr[]
brr.append(arr[0])
brr.append(arr[1])
# Iterate over the length of
# subarray
for i in range(2, N // 2 + 1):
# If array can be divided into
# subarray of i equal length
if (N % i == 0):
a = False
n = len(brr)
j = i
# Check if on repeating the
# current subarray gives the
# original array or not
while (j < N):
K = j % i
if (arr[j] == brr[K]):
j += 1
else:
a = True
break
# Subarray found
if (not a and j == N):
printArray(brr)
return
# Add current element into
# subarray
brr.append(arr[i])
# No subarray found
print("-1")
return
# Driver Code
if __name__ =="__main__":
arr = [ 1, 2, 2, 1, 2,
2, 1, 2, 2 ]
N = len(arr)
# Function call
RepeatingSubarray(arr, N)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the array
static void printArray(List<int> brr)
{
foreach(int it in brr)
{
Console.Write(it + " ");
}
}
// Function to find the smallest subarray
static void RepeatingSubarray(int []arr, int N)
{
// Corner Case
if (N < 2)
{
Console.Write("-1");
}
// Initialize the auxiliary subarray
List<int> brr = new List<int>();
// Push the first 2 elements into
// the subarray brr[]
brr.Add(arr[0]);
brr.Add(arr[1]);
// Iterate over the length of
// subarray
for(int i = 2; i < N / 2 + 1; i++)
{
// If array can be divided into
// subarray of i equal length
if (N % i == 0)
{
bool a = false;
int n = brr.Count;
int j = i;
// Check if on repeating the
// current subarray gives the
// original array or not
while (j < N)
{
int K = j % i;
if (arr[j] == brr[K])
{
j++;
}
else
{
a = true;
break;
}
}
// Subarray found
if (!a && j == N)
{
printArray(brr);
return;
}
}
// Add current element into
// subarray
brr.Add(arr[i]);
}
// No subarray found
Console.Write("-1");
return;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 2, 1,
2, 2, 1, 2, 2};
int N = arr.Length;
// Function call
RepeatingSubarray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to print the array
function printArray(brr)
{
for (let it of brr) {
document.write(it + ' ');
}
}
// Function to find the smallest subarray
function RepeatingSubarray(arr, N)
{
// Corner Case
if (N < 2) {
document.write("-1");
}
// Initialize the auxiliary subarray
let brr = [];
// Push the first 2 elements into
// the subarray brr[]
brr.push(arr[0]);
brr.push(arr[1]);
// Iterate over the length of
// subarray
for (let i = 2; i < Math.floor(N / 2) + 1; i++) {
// If array can be divided into
// subarray of i equal length
if (N % i == 0) {
let a = false;
let n = brr.length;
let j = i;
// Check if on repeating the
// current subarray gives the
// original array or not
while (j < N) {
let K = j % i;
if (arr[j] == brr[K]) {
j++;
}
else {
a = true;
break;
}
}
// Subarray found
if (!a && j == N) {
printArray(brr);
return;
}
}
// Add current element into
// subarray
brr.push(arr[i]);
}
// No subarray found
document.write("-1");
return;
}
// Driver Code
let arr = [ 1, 2, 2, 1, 2,
2, 1, 2, 2 ];
let N = arr.length;
// Function call
RepeatingSubarray(arr, N);
// This code is contributed by Surbhi Tyagi.
</script>
1 2 2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por vatsalanarang y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA