CODEWITHSUNDEEP
c++calgorithmoptimization
shubhendu
shubhendu

Reputation: 351

How to make my program work faster?

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.

my execution time is just exceeding by .0015 seconds!

#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;
}

Upvotes: 0

Views: 291

Answers (3)

b.buchhold
b.buchhold

Reputation: 3896

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

Upvotes: 3

Stan Holodnak
Stan Holodnak

Reputation: 105

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?

Upvotes: -1

alirakiyan
alirakiyan

Reputation: 428

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.

Upvotes: 0

Related Questions