Compruebe si la suma de cualquier subarreglo es palíndromo o no

Dada una array arr[] de tamaño N . la tarea es verificar si existe algún subarreglo de tamaño al menos 2 tal que su suma sea palíndromo. Si tal subarreglo existe, imprima SÍ . De lo contrario, imprima NO .
Ejemplos: 
 

Entrada: array[] = {10, 6, 7, 9, 12} 
Salida: Sí 
Explicación: 
El subarreglo [6, 7, 9] con suma 22 es palíndromo.
Entrada: arr[] = {15, 4, 8, 2} 
Salida: No 
Explicación: 
No existe tal subarreglo. 
 

Enfoque: 
Para resolver el problema, siga los pasos a continuación: 
 

• Cree una array de suma de prefijos de la array dada.
• Iterar sobre la array usando bucles for anidados para indicar el inicio y el final de las subarreglas. La suma del subarreglo dentro de los índices [x, y] se puede obtener mediante pref[y] – pref[x – 1] .
• Comprueba si esta suma es palíndromo o no. Si alguno de la suma es palíndromo escriba “Sí”, de lo contrario escriba “No”.

A continuación se muestra la implementación del enfoque anterior:
 

// 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 not
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 not
void 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 code
int main()
{
    int ar[] = { 1, 11, 20, 35 };
 
    int n = sizeof(ar) / sizeof(ar[0]);
 
    findSubarray(ar, n);
 
    return 0;
}

// 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 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 not
def 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 not
def 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 code
if __name__ == '__main__':
     
    ar = [ 1, 11, 20, 35 ]
    n = len(ar)
     
    findSubarray(ar, n)
 
# This code is contributed by Surendra_Gangwar

// C# program to check if sum of any
// subarray of size atleast 2 is
// palindrome or not
using System;
 
class GFG{
 
// Function which checks whether
// a given number is palindrome or not
static 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 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
    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 code
public static void Main()
{
    int []ar = { 1, 11, 20, 35 };
    int n = ar.Length;
 
    findSubarray(ar, n);
}
}
 
// This code is contributed by Code_Mech

<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 not
function 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 not
function 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 code
var ar = [1, 11, 20, 35];
var n = ar.length;
findSubarray(ar, n);
 
 
</script>

Yes

Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)