×

# SPALNUM - Editorial

Author: Sergey Kulik
Tester: Yanpei Liu
Editorialist: Pawel Kacprzak

SIMPLE

# PROBLEM:

Let palindromic number be a number whose decimal digits form a palindrome. For example, $1, 22, 414, 5335$ are palindromic numbers, while $13$ and $453$ are not. Your task is to find the sum of all palindromic numbers in a range $[L, R]$ inclusive. In one test file, you have to solve this task for at most 100 test cases.

# QUICK EXPLANATION:

Precompute the sum of palindromic number not greater than $K$, for $1 \leq K \leq 10^5$, and store these values in an array. Provide an answer for a single test case $[L, R]$ using precomputed sums for $R$ and $L - 1$.

# EXPLANATION:

Let's first consider solving the problem for a single test cases. We are given two number $L$ and $R$ and we have to compute the sum of palindromic numbers from $L$ to $R$ inclusive. If we can check if a number $N$ is palindromic, then we can iterate over all numbers $N$ in a range $[L, R]$ and add $N$ to the result if and only if $N$ is palindromic. How to check if a number $N$ is palindromic? Well, it is pretty straightforward, we can list the sequence of digits of $N$ from right to left, and check if that sequence is a palindrome comparing corresponding digits. A pseudocode of that method can look like that:

// we assume that N > 0
bool is_palindromic(N):
digits = [ ]
while N > 0:
digits.append(N % 10)
N /= 10
i = 0
j = digits.size() - 1
while i < j:
if digits[i] != digits[j]:
return False
i += 1
j -= 1
return True


This check runs in $O(\log(N))$ time, because the decimal representation of $N$ has $O(\log(N))$ digits.

Being able to perform the palindromic check, we can accumulate the result iterating over all integers in range $[L, R]$. A pseudocode for it might look like this:

res = 0
for N = L to R:
if is_palindromic(N):
res += N


This method works in $O((R - L) \cdot \log(R))$ time for a single test case, but since we have to handle at most $100$ of them and a range $[L, R]$ can have up to $10^5$ elements, this method will pass only the first subtask and will timeout on the second.

## How to speed it up?

The crucial observation here is that, during the whole computation described above, we might check in a number $N$ is palindromic many times! This is not good, but fortunately, there is a common technique to avoid that.

Often when we are asked many times to compute some result for objects in some range [$A, B]$, we can do the following:

Let $F[N] := \texttt{the result for a range } [0, N]$

If we are able to compute $F[N]$ for all possible $N$, then the answer for a single query $[A, B]$ equals $F[B] - F[A - 1]$, because $F[B]$ contains the result for all numbers not greater than $B$, so if we subtract $F[A - 1]$, i.e the result for all number smaller than $A$, from it, we will get the result for all numbers in range $[A, B]$.

If you did not know this technique, please remember it, because it is very useful.

Using the above method, we can precompute:

$S[N] := \texttt{sum of palindromic number not greater than } N$

in the following way:

S[0] = 1
for N = 1 to 100000:
S[N] = S[N - 1]
if is_palindromic(N):
S[N] += N


The above method runs in $O(10^5 \cdot \log(10^5))$ time, and we can use the S table to answer any single query $[L, R]$ in a constant time.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

70483685
accept rate: 12%

15.4k347484505

Practice link redirects to Pattern Matching Problem.

(27 Sep '15, 16:30)

What's the name of the technique, you have mentioned? So, that we know more about it using that keyword?

(24 Jul, 23:28) 2★

 1 I didn't use the method given for speeding up the queries but still my solution didn't timed out. Don't know why??? https://www.codechef.com/viewsolution/8256629 and the links for problem statement are wrong. answered 27 Sep '15, 14:37 11 accept rate: 0%
 0 I used same approach as given above but still it was showing wrong answer. https://www.codechef.com/viewsolution/8260332 answered 27 Sep '15, 14:42 31●2 accept rate: 0% it is not giving correct answer even for test cases. u can have a look at https://www.codechef.com/viewsolution/8253282 (27 Sep '15, 15:08) likecs6★ i know that but if you look at my program and the approach mentioned above ,you will find that both are exactly same. If anyone can tell where i am wrong. (27 Sep '15, 15:45)
 0 The link provided for author's and tester's solution is not valid. Please check answered 27 Sep '15, 18:31 21●1 accept rate: 0%
 0 We can also try the below approach: Start with L, sum=0 Find Next Palindrome Number, //complexity O(Log(10^5)) if PalindromeNumber <= R  Sum+=PalindromeNumber  else  return sum  Repeat Step 2 // O(10^4) Total Complexity would be Number of Testcases X 10^4 X O(Log(10^5)) What do you think? For a single test case this should be better solution. link This answer is marked "community wiki". answered 27 Sep '15, 18:39 1●1 accept rate: 0%
 0 Help , Why this code : http://ideone.com/WIZx1G give WA even the test case same like the problem , can someone give me some of explanation ? answered 27 Sep '15, 21:05 2★harry30 1 accept rate: 0% You have not included right limit 'b' which is supposed to be included. Question asks you to include both the given numbers in the sum if they are palindromes. Try the testcase 1 11 where your code produces 45 while the correct answer should be 56 (28 Sep '15, 17:42)

# include<bits stdc++.h="">

using namespace std;

# define n 312457

int digits[20]; int k=0; int sum[n]={0}; bool isp(int x) { int m,j,k=0; while(x>0) {

    digits[k]=x%10;
x=x/10;
k++;
}
for(int i = 0, j = k - 1; i < k; ++i, --j)
{
if(digits[i]!=digits[j])
{
return false;
}

}

return true;


}

void pre() { for(int p=1;p<=1000;p++) { if(isp(p)==true) { sum[p]=p; } sum[p]+=sum[p-1]; } }

int main() { long long int i,j,k,t,l,r; cin>>t; pre(); while(t--) {

    cin>>l;
cin>>r;
cout<<sum[r]-sum[l-1]<<endl;

}

return 0;


}

11
accept rate: 0%

 0 can we not do this without using array. my code is giving wrong answer. can someone explain me why. https://www.codechef.com/viewsolution/8801313. please answered 17 Nov '15, 17:30 0★ps_3790 1 accept rate: 0%

# include<stdio.h>

int main() { int t,l[100],r[100],i,j,rev=0,sum=0,dig,n; scanf("%d",&t); printf("\n"); for(i=0;i<t;i++) { scanf("%d %d",&l[i],r[i]); printf("\n"); } for(i=0;i<t;i++) { sum=0; if(l[i]<=r[i]) { for(j=l[i];j<=r[i];j++) { l[i]=n; rev=0; while(n) { dig=n%10; rev=rev10+dig; n=n/10; } } if(l[i]==rev) { sum=sum+l[i]; } } else { for(j=r[i];j<=l[i];j++) { r[i]=n; rev=0; while(n) { dig=n%10; rev=rev10+dig; n=n/10; } if(r[i]==rev) { sum=sum+r[i]; } } } printf("%d\n",sum); } return 0; }

1
accept rate: 0%

its showing run time error. can anyone tell me what is this run time error??

(14 Jan '16, 13:43)

I tried this code but it was good only for subtask 1 and not for subtask 2. Can anyone tell me why?

# include<string.h>

int main(){ int cases,k; scanf("%d",&cases); for(k=0;k<cases;++k){ long int a,b,len,i,sum=0;

    scanf("%li%li",&a,&b);
while(a<=b){
char str[8];
int palin=1;

sprintf(str,"%li",a);

len=strlen(str);

for(i=0;i<=(len/2);++i){
if(str[i]!=str[(len-1)-i]){
palin=0;
break;
}
}
if(palin==1)
sum+=a;

a++;
}

printf("%li\n",sum);
}
return 0;


}

1
accept rate: 0%

I tried this code but it was good only for subtask 1 and not for subtask 2. Can anyone tell me why?

# include<string.h>

int main(){ int cases,k; scanf("%d",&cases); for(k=0;k<cases;++k){ long int a,b,len,i,sum=0;

    scanf("%li%li",&a,&b);
while(a<=b){
char str[8];
int palin=1;

sprintf(str,"%li",a);

len=strlen(str);

for(i=0;i<=(len/2);++i){
if(str[i]!=str[(len-1)-i]){
palin=0;
break;
}
}
if(palin==1)
sum+=a;

a++;
}

printf("%li\n",sum);
}
return 0;


}

1
accept rate: 0%

 0 You can also reverse the number and then compare it with the original number to find out if the number is a palindrome or not.It works for both all the test cases. answered 28 Jan '16, 18:25 2★jayanti 1 accept rate: 0%
 0 is it necessary to take the help of data structrure (array) answered 25 Mar '16, 05:30 2★k1941996 1 accept rate: 0%
 0 why the decimal representation of N have log(N) digits? answered 05 Jul '16, 17:20 1 accept rate: 0% Here, the base of log is not 2, not 10. That's why. (27 Jun, 16:29)
 0 Wow! This method is freaking amazing! My program execution time decreased from 1.30 seconds to 0.06 seconds. The change is amazing! Wow! answered 27 Jun, 16:20 248●8 accept rate: 0%
 0 Can Anyone can explain the following lines, how it works? I'm not getting it. Examples might be used to better explaination. Thanks In Advance. query [A,B][A,B] equals F[B]−F[A−1] answered 24 Jul, 22:48 2★jvjplus 0 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×10,871
×744
×742
×147
×35

question asked: 20 Sep '15, 22:38

question was seen: 4,970 times

last updated: 24 Jul, 23:29