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(N3)
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> |
-1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!