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 subarraybool 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 indexint 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 Codeint 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 approachimport 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 subarraydef 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 = 4ans = 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 approachusing 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 subarraypublic 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 indexstatic 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 codepublic 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] There you will find 78503 more Information on that Topic: geeksforgeeks.org/subarray-of-length-k-whose-concatenation-forms-a-palindrome/ […]
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/subarray-of-length-k-whose-concatenation-forms-a-palindrome/ […]