3
\$\begingroup\$

This is my solution to the competitive coding question on SPOJ here. It gives a runtime of 0.24 but the best solutions posted have a 0.0 runtime. How could I possibly achieve better results than this?

#include<iostream>
#include<cstdio>

using namespace std;

int rev(int num)
{
    int rev_num=0;
    while(num)
    {
        rev_num= rev_num*10 + num%10;
        num/=10;
    }
    return rev_num;
}
int main()
{   
    int n, n1, n2;
    scanf("%d",&n);
    while(n--)
    {
        cin>>n1>>n2;
        cout<<rev(rev(n1)+rev(n2))<<endl;

    }
    return 0;
}
\$\endgroup\$
2
\$\begingroup\$

A faster method would avoid the numeric divisions. Instead, it would load the number in a string (through the sprintf function), reverse the string, and finally recast the string into a number (with the help of the sscanf function).

I'm attaching a function named fastrev which in turn uses an auxilliary function reverse_string. Hopefully, this would improve runtime for large numbers.

char* reverse_string(char *s1, char* s2)
{
    char *p, *q;
    int len = strlen(s1);

    for (p = s1; *p; p++) {
        s2[len-1] = *p;
        len--;
    }
    return s2;
}

int fastrev(int num) {
    static char nbuff[32];
    static char rnbuff[32];
    int rnum;

    sprintf(nbuff, "%d", num);
    reverse_string(nbuff, rnbuff);
    sscanf(rnbuff, "%d", &rnum);
    return rnum;
}
\$\endgroup\$
  • \$\begingroup\$ 's2[len] = '\0';' is needed before the for loop in the reverse_string function to reset s2 before each use so that the trailing characters from the previous reversal are not considered this time. Other than that, good alternative. But it increases the time to 0.38. I think all the memeory read/write of the char arrays is to blame. \$\endgroup\$ – kSureja Jun 18 '14 at 21:03
  • \$\begingroup\$ Actually no... Recall that s2 points to the rnbuff which is statically allocated and hence initialized to all zeroes. Memory read/write shouldn't be an issue because it is very fast... The Disk I/O is expected to be slow... How exactly are you measuring the runtime? If you want to squeeze runtime to the extreme possible extent, you might swap a[0] with a[n-1], a[1] with a[n-2] and so on... then you wont require the second buffer.... \$\endgroup\$ – Debasis Jun 18 '14 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.