Subarreglo de longitud K cuya concatenación forma un palíndromo

Dada una array arr[] , que consta de N enteros en el rango [0, 9] , la tarea es encontrar una subarreglo de longitud K a partir de la cual podamos generar un número que sea un número palíndromo . Si no existe tal subarreglo, imprima -1 .

Nota: Los elementos de la array están en el rango de 0 a 10.

Ejemplos:

Entrada: arr[] = {1, 5, 3, 2, 3, 5, 4}, K = 5
Salida: 5, 3, 2, 3, 5
Explicación:
Número generado al concatenar todos los elementos del subarreglo, es decir, 53235 , es un palíndromo.

Entrada: arr[] = {2, 3, 5, 1, 3}, K = 4
Salida: -1

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos de longitud K y, para cada subarreglo, concatenar todos los elementos del subarreglo y verificar si el número formado es un número palíndromo o no. 

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

Enfoque eficiente: el problema se puede resolver utilizando la técnica de deslizamiento de ventanas . Siga los pasos a continuación para resolver el problema:

• Haga una función de palíndromo para verificar si el subarreglo dado (Ventana deslizante) es palíndromo o no.
• Itere sobre la array y, para cada subarreglo, llame a la función palíndromo.
• Si se determina que es cierto, devuelve el índice inicial de ese subarreglo e imprime el arreglo desde el índice inicial hasta el siguiente índice k.
• Si no se encuentra tal subarreglo, que es un palíndromo, imprima -1.

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 check if a number
// is Palindrome or not
// here i is the starting index
// and j is the last index of the subarray
bool palindrome(vector<int> a, int i, int j)
{
     while(i<j)
     {
         // If the integer at i is not equal to j
         // then the subarray is not palindrome
         if(a[i] != a[j])
             return false;
              
         // Otherwise
         i++;
         j--;
     }
          
     // all a[i] is equal to a[j]
     // then the subarray is palindrome
     return true;
}
 
// Function to find a subarray whose
// concatenation forms a palindrome
// and return its starting index
int findSubArray(vector<int> arr, int k)
{
    int n= sizeof(arr)/sizeof(arr[0]);
         
    // Iterating over subarray of length k
    // and checking if that subarray is palindrome
    for(int i=0; i<=n-k; i++){
         if(palindrome(arr, i, i+k-1))
             return i;
    }
       
    // If no subarray is palindrome
    return -1;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 3, 5, 1, 3 };
    int k = 4;
  
    int ans = findSubArray(arr, k);
  
    if (ans == -1)
  
        cout << -1 << "\n";
  
    else {
        for (int i = ans; i < ans + k;
             i++)
            cout << arr[i] << " ";
        cout << "\n";
    }
    return 0;
}
 
// This code is contributed by Prafulla Shekhar

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
    // Function to check if a number
    // is Palindrome or not
    // here i is the starting index
    // and j is the last index of the subarray
    public static boolean palindrome(int[] a, int i, int j)
    {
         while(i<j)
         {
             // If the integer at i is not equal to j
             // then the subarray is not palindrome
             if(a[i] != a[j])
                 return false;
              
             // Otherwise
             i++;
             j--;
         }
          
         // all a[i] is equal to a[j]
         // then the subarray is palindrome
         return true;
     }
   
    // Function to find a subarray whose
    // concatenation forms a palindrome
    // and return its starting index
    static int findSubArray(int []arr, int k)
    {
        int n= arr.length;
         
        // Iterating over subarray of length k
        // and checking if that subarray is palindrome
        for(int i=0; i<=n-k; i++){
             if(palindrome(arr, i, i+k-1))
                 return i;
        }
       
        // If no subarray is palindrome
        return -1;
    }
 
    // Driver code
    public static void main (String[] args)
    {
        int []arr = { 2, 3, 5, 1, 3 };
        int k = 4;
  
        int ans = findSubArray(arr, k);
  
        if (ans == -1)
            System.out.print(-1 + "\n");
  
        else
        {
            for(int i = ans; i < ans + k; i++)
                System.out.print(arr[i] + " ");
              
            System.out.print("\n");
        }
    }
}
 
// This code is contributed by Prafulla Shekhar

# Python3 program for the above approach
 
# Function to check if a number
# is Palindrome or not here i is
# the starting index and j is the
# last index of the subarray
def palindrome(a, i, j):
     
    while(i < j):
         
        # If the integer at i is not equal to j
        # then the subarray is not palindrome
        if (a[i] != a[j]):
            return False
       
        # Otherwise
        i += 1
        j -= 1
     
    # all a[i] is equal to a[j]
    # then the subarray is palindrome
    return True
 
# Function to find a subarray whose
# concatenation forms a palindrome
# and return its starting index   
def findSubArray(arr, k):
     
    n = len(arr)
     
    # Iterating over subarray of length k
    # and checking if that subarray is palindrome  
    for i in range(n - k + 1):
        if (palindrome(arr, i, i + k - 1)):
            return i
     
    return -1
 
# Driver code   
arr = [ 2, 3, 5, 1, 3 ]
k = 4
ans = findSubArray(arr, k)
 
if (ans == -1):
    print(-1)
else:
    for i in range(ans,ans + k):
        print(arr[i], end = " ")
         
# This code is contributed by avanitrachhadiya2155

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if a number
// is Palindrome or not here i is
// the starting index and j is the
// last index of the subarray
public static bool palindrome(int[] a, int i,
                              int j)
{
    while (i < j)
    {
         
        // If the integer at i is not equal to j
        // then the subarray is not palindrome
        if (a[i] != a[j])
            return false;
 
        // Otherwise
        i++;
        j--;
    }
 
    // All a[i] is equal to a[j]
    // then the subarray is palindrome
    return true;
}
 
// Function to find a subarray whose
// concatenation forms a palindrome
// and return its starting index
static int findSubArray(int[] arr, int k)
{
    int n = arr.Length;
     
    // Iterating over subarray of length k
    // and checking if that subarray is palindrome
    for(int i = 0; i <= n - k; i++)
    {
        if (palindrome(arr, i, i + k - 1))
            return i;
    }
 
    // If no subarray is palindrome
    return -1;
}
 
// Driver code
public static void Main(String[] args)
{
    int[] arr = { 2, 3, 5, 1, 3 };
    int k = 4;
    int ans = findSubArray(arr, k);
 
    if (ans == -1)
        Console.Write(-1 + "\n");
         
    else
    {
        for(int i = ans; i < ans + k; i++)
            Console.Write(arr[i] + " ");
 
        Console.Write("\n");
    }
}
}
 
// This code is contributed by aashish1995

<script>
 
// Javascript program for
// the above approach
 
    // Function to check if a number
    // is Palindrome or not
    // here i is the starting index
    // and j is the last index of the subarray
    function palindrome(a, i, j)
    {
         while(i<j)
         {
             // If the integer at i is not equal to j
             // then the subarray is not palindrome
             if(a[i] != a[j])
                 return false;
               
             // Otherwise
             i++;
             j--;
         }
           
         // all a[i] is equal to a[j]
         // then the subarray is palindrome
         return true;
     }
    
    // Function to find a subarray whose
    // concatenation forms a palindrome
    // and return its starting index
    function findSubArray(arr, k)
    {
        let n= arr.length;
          
        // Iterating over subarray of length k
        // and checking if that subarray is palindrome
        for(let i=0; i<=n-k; i++){
             if(palindrome(arr, i, i+k-1))
                 return i;
        }
        
        // If no subarray is palindrome
        return -1;
    }
     
// Driver Code
     
         let arr = [ 2, 3, 5, 1, 3 ];
        let k = 4;
   
        let ans = findSubArray(arr, k);
   
        if (ans == -1)
            document.write(-1 + "\n");
   
        else
        {
            for(let i = ans; i < ans + k; i++)
                document.write(arr[i] + " ");
               
            document.write("<br/>");
        }
 
</script>

-1

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