Palindromic Sum
Practice
3.5 (2 votes)
Linear algebra
Fast fourier transform
Medium Hard
Mathematics
Problem
9% Success 364 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Given an array A of length N, find the number of non empty sub-arrays such that sum of all the elements in the sub-array is a palindrome. In other words, you have to find number of pairs \((i,\;j)\) such that \(\sum_{x=i}^j A_x\) is a palindrome where \((1 \le i \le j \le N)\).

Input Format:
First line contains an integer, N \((1 \le N \le 5 * 10^5)\). Second line contains N space separated integers, \(A_i\) \((1 \le A_i \le 2 * 10^6)\), elements of the array A. The sum of all the elements in the array is in the range \([1, 2 * 10^6]\).

Output Format:
Print an integer, number of non empty sub-arrays such that sum of all the elements in the sub-array is a palindrome.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
12 votes
Tags:
Linear AlgebraFast Fourier transformFourier TransformationsWalsh-Hadarm transformMedium-HardModular exponentiationMathematics
Points:50
2 votes
Tags:
MathematicsWalsh-Hadarm transformFast Fourier transformMedium-HardLinear Algebra