How to make my program work faster?

Question

I tried to run this code but it shows time limit exceeded in few cases, how can i shorten the time?

I need to understand what I have used in my program for which time is taking much, like some functions etc.. I understand by improving the iteration and complexity i can reduce execution time but its not helping much.please help

The program is simple, I take point a and point b and calculate the numbers of all the palindrome numbers.

#include<stdio.h>
int ifpalin(int g)
{
    int rev=0;
    int tmp=g;
    while(tmp>0)
    {
        rev=rev*10+(tmp%10);
        tmp=tmp/10;
    }
    if(rev==g)
        return 1;
    else
        return 0;
}
int findpalin(int a1,int b1)
{
    int sm=0;
    for(int i=a1;i<=b1;i++)
    {
      if  (ifpalin(i)==1)
        sm++;
    }
    printf("%d",sm);
    printf("\n");
    return 0;
}
int main()
{
int a,b,n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        scanf("%d",&b);
        findpalin(a,b);
    }
    return 0;
}

If this code "works", but is not performant enough, [codereview.stackexchange.com](http://codereview.stackexchage.com) is probably a better fit for your post. — WhozCraig, Nov 06 '16 at 08:44
Don't reverse the whole thing. Stop when you don't match or get half way through. — user4581301, Nov 06 '16 at 08:54
Interesting question. There are a couple of things you may do to optimize your program. You can get rid of at least one if-test by returning rev from ifpalin(), and then compare the returned value with i in findpalin(). Another potential optimization (measure it) is to replace the modulus and division of tmp with one call to div(). — Bjorn A., Nov 06 '16 at 08:55
yes, @user4581301 i exactly did that way but still it shows the problem, I did this. for even length numbers I check the length for 0 to n/2 if equal to n/2+1 to l and in odd ones 0 to floor n/2 and floor n/2 to l ,giving right answer but still time limit exceeding — shubhendu, Nov 06 '16 at 09:33
@BjornA. ok, am trying it now, will update if it works better :) — shubhendu, Nov 06 '16 at 09:34
Your code is not only 0.0015 secs slower than it should be. It just gets terminated after exceeding the time limit. It's much slower than that. You need to use a more efficient algorithm. — kraskevich, Nov 06 '16 at 11:48

b.buchhold · Accepted Answer · 2017-04-10T14:20:27.587

Your code is already pretty efficient (as an implementation of your algorithm, which is the thing that can be improved). These challenges want to you to find a "non-obvious", but more efficient, algorithm. I.e., in this particular case, you should not check every number between a and b.

There is another solution here, i.e. you can "know" the number of palidromes directly. Think about it´like this:

With one digit, there are 10 palidromes [0, ..., 9],

With two digits, there are 9 palindromes [11, ..., 99].

With three digits, there are 9 possibilities where the first and last digit are equal [1, ..., 9]. For a viable palindrom, the middle has to be a palindrome as well. Since the middle has one digit, we know there are 10 possibilities for palindromes here and thus we have 9 * 10 = 90 palindromes with 3 digits.

With four digits, we got 9 * 10 (two-digit palindromes, 00 now also allowed) and with 5 digits 9 * 100 (3-digit p, starting with 0 allowed).

Thus you can derive a formula for n-digit numbers. Then, you can directly derive the number for large streaks between a and b and only have to worry about which number of digits are relevant and how many numbers are lost in the beginning and end due to a and b not being 10^(n-1) and and 10^n - 1

score 0 · Answer 2 · answered Nov 06 '16 at 10:41

Your int ifpalin(int g) fnction, for each given g, could be run in parallel because it seems like different input data for this function, has no effect on other data. you can run this function in parallel.

In int findpalin(int a1,int b1) function, there is a for loop which its complexity order is N, this is where you can run your threads. (each thread, runs function ifpalin). Of course, a good parallelism plan is needed. You can run this function in some logical bunch, and aggregate the results.

On the other hand, any benchmark should be performed in release mode.

I hope it helps.

Excuse me if my writing in English is bad, and please correct me.

score -1 · Answer 3 · edited May 23 '17 at 11:54

-1

In ifpalin
Convert the number to string 
Reverse the string
Compare with the original
If equal then it's a palindrome

See How to reverse an std::string?

edited May 23 '17 at 11:54

Community

1
1

answered Nov 06 '16 at 09:40

Stan Holodnak

105
2

Converting a number to a string involves modulus and division, it's just that it happens in the sprintf function instead of explicitly. – Steve Nov 06 '16 at 11:01
The point is to convert a number to string or const char * and then reverse it and "==" with the original. That's how you know if left2right = right2left – Stan Holodnak Nov 06 '16 at 12:20
I know what you're saying, but that approach will not speed up the algorithm which is the point of the question. – Steve Nov 06 '16 at 14:22
You almost have something here, Stan. The trick is to eliminate the need to convert number <-> string in the first place and stay in strings the whole way through. – user4581301 Nov 06 '16 at 16:04

How to make my program work faster?

3 Answers3