Subarray of length K whose concatenation forms a palindrome

0 0 6 minutes read

Given an array arr[], consisting of N integers in the range [0, 9], the task is to find a subarray of length K from which we can generate a number which is a Palindrome Number. If no such subarray exists, print -1.

Note: The elements in the array are in the range of 0 to 10.

Examples:

Input: arr[] = {1, 5, 3, 2, 3, 5, 4}, K = 5
Output: 5, 3, 2, 3, 5
Explanation:
Number generated by concatenating all elements of the subarray, i.e. 53235, is a palindrome.

Input: arr[] = {2, 3, 5, 1, 3}, K = 4
Output: -1

Naive Approach: The simplest approach to solve the problem is to generate all subarrays of length K and for each subarray, concatenate all the elements from the subarray and check if the number formed is a Palindrome Number or not.

Time Complexity: O(N³)
Auxiliary Space: O(K)

Efficient Approach: The problem can be solved using the Window-Sliding technique. Follow the steps below to solve the problem:

Make a palindrome function to check if the given subarray (Window-Sliding) is palindrome or not.
Iterate over the array, and for each subarray call the palindrome function.
If found to be true, return the starting index of that subarray, and print the array from starting index to the next k index.
If no such subarray found which is a palindrome, print -1.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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

Javascript

<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>

Output

-1

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!