Given an array arr[] of size N. the task is to check whether there exists any subarray of size atleast 2 such that its sum is palindrome. If such a subarray exists, then print YES. Otherwise, print NO.
Examples:
Input: arr[] = {10, 6, 7, 9, 12}
Output: Yes
Explanation:
The subarray [6, 7, 9] with sum 22 is palindrome.
Input: arr[] = {15, 4, 8, 2}
Output: No
Explanation:
No such subarray exists.
Approach:
To solve the problem follow the steps below:
- Create a prefix sum array of the given array.
- Iterate over the array using nested for loops to denote start and end of subarrays. The sum of the subarray within the indices [x, y] can be obtained by pref[y] – pref[x – 1].
- Check if this sum is Palindrome or not. If any of the sum if palindrome print “Yes”, otherwise print “No”.
Below is the implementation of above approach:
C++
// C++ program to check if sum of any// subarray of size atleast 2 is// palindrome or not#include <bits/stdc++.h>using namespace std;// Function which checks whether// a given number is palindrome or notbool checkPalindrome(int n){ // Store the reverse of // the number n int rev = 0; for (int x = n; x != 0; x /= 10) { int d = x % 10; rev = rev * 10 + d; } if (rev == n) return true; else return false;}// Function which checks if the// requires subarray exists or notvoid findSubarray(int ar[], int n){ // Making a prefix sum array of ar[] int pref[n]; pref[0] = ar[0]; for (int x = 1; x < n; x++) pref[x] = pref[x - 1] + ar[x]; // Boolean variable that will store // whether such subarray exists or not bool found = false; for (int x = 0; x < n; x++) { for (int y = x + 1; y < n; y++) { // sum stores the sum of subarray // from index x to y of array int sum = pref[y]; if (x > 0) { sum -= pref[x - 1]; } if (checkPalindrome(sum)) { // Required subarray is found found = true; break; } } if (found) break; } if (found) cout << "Yes" << endl; else cout << "No" << endl;}// Driver codeint main(){ int ar[] = { 1, 11, 20, 35 }; int n = sizeof(ar) / sizeof(ar[0]); findSubarray(ar, n); return 0;} |
Java
// Java program to check if sum of any // subarray of size atleast 2 is // palindrome or not class GFG{ // Function which checks whether // a given number is palindrome or not static boolean checkPalindrome(int n) { // Store the reverse of // the number n int rev = 0; for(int x = n; x != 0; x /= 10) { int d = x % 10; rev = rev * 10 + d; } if (rev == n) return true; else return false; } // Function which checks if the // requires subarray exists or not static void findSubarray(int []ar, int n) { // Making a prefix sum array of ar[] int []pref = new int[n]; pref[0] = ar[0]; for(int x = 1; x < n; x++) pref[x] = pref[x - 1] + ar[x]; // Boolean variable that will store // whether such subarray exists or not boolean found = false; for(int x = 0; x < n; x++) { for(int y = x + 1; y < n; y++) { // sum stores the sum of subarray // from index x to y of array int sum = pref[y]; if (x > 0) { sum -= pref[x - 1]; } if (checkPalindrome(sum)) { // Required subarray is found found = true; break; } } if (found) break; } if (found) System.out.println("Yes"); else System.out.println("No"); } // Driver code public static void main(String args[]) { int []ar = { 1, 11, 20, 35 }; int n = ar.length; findSubarray(ar, n); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to check if sum of # any subarray of size atleast 2 is# palindrome or not# Function which checks whether a # given number is palindrome or notdef checkPalindrome(n): # Store the reverse # of the number n rev = 0 x = n while(x != 0): d = x % 10 rev = rev * 10 + d x = x // 10 if (rev == n): return True else: return False# Function which checks if the# requires subarray exists or notdef findSubarray(ar, n): # Making a prefix sum array of ar[] pref = [0 for i in range(n)] pref[0] = ar[0] for x in range(1, n): pref[x] = pref[x - 1] + ar[x] # Boolean variable that will store # whether such subarray exists or not found = False for x in range(n): for y in range(x + 1, n, 1): # Sum stores the sum of subarray # from index x to y of array sum = pref[y] if (x > 0): sum -= pref[x - 1] if (checkPalindrome(sum)): # Required subarray is found found = True break if (found): break if (found): print("Yes") else: print("No")# Driver codeif __name__ == '__main__': ar = [ 1, 11, 20, 35 ] n = len(ar) findSubarray(ar, n)# This code is contributed by Surendra_Gangwar |
C#
// C# program to check if sum of any// subarray of size atleast 2 is// palindrome or notusing System;class GFG{// Function which checks whether// a given number is palindrome or notstatic bool checkPalindrome(int n){ // Store the reverse of // the number n int rev = 0; for(int x = n; x != 0; x /= 10) { int d = x % 10; rev = rev * 10 + d; } if (rev == n) return true; else return false;}// Function which checks if the// requires subarray exists or notstatic void findSubarray(int []ar, int n){ // Making a prefix sum array of ar[] int []pref = new int[n]; pref[0] = ar[0]; for(int x = 1; x < n; x++) pref[x] = pref[x - 1] + ar[x]; // Boolean variable that will store // whether such subarray exists or not bool found = false; for(int x = 0; x < n; x++) { for(int y = x + 1; y < n; y++) { // sum stores the sum of subarray // from index x to y of array int sum = pref[y]; if (x > 0) { sum -= pref[x - 1]; } if (checkPalindrome(sum)) { // Required subarray is found found = true; break; } } if (found) break; } if (found) Console.WriteLine("Yes"); else Console.WriteLine("No");}// Driver codepublic static void Main(){ int []ar = { 1, 11, 20, 35 }; int n = ar.Length; findSubarray(ar, n);}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program to check if sum of any// subarray of size atleast 2 is// palindrome or not// Function which checks whether// a given number is palindrome or notfunction checkPalindrome(n){ // Store the reverse of // the number n var rev = 0; for (var x = n; x != 0; x = parseInt(x/10)) { var d = x % 10; rev = rev * 10 + d; } if (rev == n) return true; else return false;}// Function which checks if the// requires subarray exists or notfunction findSubarray(ar, n){ // Making a prefix sum array of ar[] var pref = Array(n).fill(0); pref[0] = ar[0]; for (var x = 1; x < n; x++) pref[x] = pref[x - 1] + ar[x]; // Boolean variable that will store // whether such subarray exists or not var found = false; for (var x = 0; x < n; x++) { for (var y = x + 1; y < n; y++) { // sum stores the sum of subarray // from index x to y of array var sum = pref[y]; if (x > 0) { sum -= pref[x - 1]; } if (checkPalindrome(sum)) { // Required subarray is found found = true; break; } } if (found) break; } if (found) document.write( "Yes" ); else document.write( "No" );}// Driver codevar ar = [1, 11, 20, 35];var n = ar.length;findSubarray(ar, n);</script> |
Output:
Yes
Time Complexity: O(n2logn)
Auxiliary Space: O(n) because using extra space for pref array
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!
