13
\$\begingroup\$

My program takes as first input the number of test cases, n. For the following n inputs, I output the smallest positive integer that has to be added to the input to make the input a numeric palindrome. If the input is already a palindrome the output shall be zero.

I have a problem with the performance, the algorithm is correct but I get get time limit exceeded. The input number is in the range \$[1, 1000000]\$.

#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;

extern bool isPal(const int &number) __attribute__((fastcall)); 

bool isPal(const int &number)
{
    char buffer[6];
    sprintf(buffer,"%i",number);
    const string x = buffer;
    for(int i=0, end = x.size()-1;i<end;i++,end--)
        if(x[i]!=x[end])
        return false;
    return true;
}

int main()
{
    int n, number, counter, t;
    scanf("%i",&n);
    while(n--)
    {
        counter = 0;
        scanf("%i",&number);
        t = number+counter;
        while(!isPal(t))
        {
            ++counter;
            t = number+counter;
        }
        printf("%i\n",counter);
    }
    return 0;
}

Please help me optimise the above code.

\$\endgroup\$
  • \$\begingroup\$ I would concentrate on the sprintf inside isPal. Replace it with integer calculations. \$\endgroup\$ – nwp Sep 29 '14 at 18:25
  • \$\begingroup\$ and on the string. That's superfluous overhead too. Anyway, shall that be C or C++? \$\endgroup\$ – Deduplicator Sep 29 '14 at 18:27
12
\$\begingroup\$

Comments on the code as it is

This:

__attribute__((fastcall))

will not improve your performance, as the culprit is the algorithm not the compiler. If you really want to tell the compiler to optimize your code harder, you can try inline instead.

This forward declaration:

extern bool isPal(const int &number) __attribute__((fastcall));

is unnecessary as the function body directly follows the forward declaration.

Looking at the isPal function the name could have been better. I would suggest isPalindrome.

bool isPal(const int &number)
{
    char buffer[6];
    sprintf(buffer,"%i",number);
    const string x = buffer;
    for(int i=0, end = x.size()-1;i<end;i++,end--)
        if(x[i]!=x[end])
        return false;
    return true;
}
  • Unless you need to modify the argument, always take simple types by value; so const int& number should be int number.
  • The input range is \$[0,1000000]\$ so your buffer is too small it needs to be at least 7 + 1 (for the null terminator).
  • The use of sprintf is discouraged, please prefer snprintf instead. You might want to consider stringstream for type conversion but I'll leave that up to you.
  • The variable const string x is unnecessary, simply use strlen from <cstring> instead.
  • You really should put some white spaces in there as the code is hard to read as it is.
  • Always prefer to use curly braces ({}) on control statements. Your missing indentation on the return false statement is confusing.
  • Also you can do without the end variable, but that's up to taste. But I will leave it there.

Fixing the above, your function should look like:

bool isPalindrome(int number)
{
    char buffer[8];
    snprintf(buffer, 8, "%i", number);
    int len = strlen(buffer);
    for(int i = 0, end = len - 1; i < end; i++, end--){
        if(buffer[i] != buffer[end]){
            return false;
        }
    }
    return true;
}

Now looking at your main() function.

  • Always prefer to declare your variables in the smallest possible scope. This makes the code easier to read. This means that counter, number and t should be declared inside of the loop body.
  • You're using C-style IO in a C++ program, this is not recommended. Instead you should use C++ streams cin and cout.
  • Again you could use some more white spaces.

The fixed code:

int main()
{
    int n;
    cin >> n;;
    while(n--)
    {
        int counter = 0;
        int number;
        cin >> number;
        int t = number + counter;
        while(!isPal(t))
        {
            ++counter;
            t = number + counter;
        }
        cout << counter << endl;
    }
    return 0;
}

Data handling improvements

You are formatting the input to a string to check if it is a palindrome. This is quite unnecessary. To test if an integer is a numeric palindrome, you need to count the number of digits in the number, then extract and flip the digits in the top half and compare them to the bottom half. Like this:

int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

int countDigits(int value){
  int digits = 0;
  while(value != 0){
    value /= 10;
    digits++;
  }
  return digits;
}

int flipDigits(int value){
  int ans = 0;
  while(value){
    ans *= 10;
    ans += value % 10;
    value /= 10;
  }
  return ans;
}

int isPalindrome(int value){
  int digits = countDigits(value);
  int ten_pow_digits_2 = ipow(10, digits/2);
  int high_digits = value / ten_pow_digits_2;
  if(digits%2){
    high_digits /= 10;
  }
  int low_digits = value % ten_pow_digits_2;

  return flipDigits(high_digits) == low_digits;
}

This will check if the number is a palindrome without formatting to a string and will be faster. However we can do better by improving the algorithm.

Algorithmic improvements

I'm not going to describe the correct algorithm here as @outoftime has already done so in his answer. Instead I'm going to provide a different implementation of the same algorithm with less code that doesn't abuse inheritance of the standard containers. You can find such improvements as predefined values and so on.

#include <iostream>

constexpr int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

// This covers the range of int.
const int pow10[]{ipow(10,0), ipow(10,1), ipow(10,2), ipow(10,3), 
    ipow(10,4), ipow(10,5), ipow(10,6), ipow(10,7), ipow(10,8), ipow(10,9) };

int countDigits(int value){
  int digits = 0;
  while(value != 0){
    value /= 10;
    digits++;
  }
  return digits;
}

int getDigit(int value, int digit){
  int place = pow10[digit];
  return (value/place) % 10;
}

int calcPalindromeDeficiency(int value){
  const int digits = countDigits(value);
  int digit = 0;
  int ans = 0;
  while(digit != (digits+1)/2){
    int top_digit = getDigit(value, digits - digit - 1);
    int bottom_digit = getDigit(value, digit);
    int to_add = ((10 + top_digit - bottom_digit)%10)*pow10[digit];
    ans += to_add;
    value += to_add;
    if(getDigit(value, digits - digit - 1) == getDigit(value, digit)){
      digit++;
    }
  }
  return ans;
}

int main(){
  int n;
  std::cin >> n;

  while(n--){
    int input;
    std::cin >> input;
    std::cout << calcPalindromeDeficiency(input) << std::endl;
  }
  return 0;
}

I find it more elegant to not convert to string when handling numbers.

\$\endgroup\$
5
\$\begingroup\$

Why your solution does not pass the time-limit test

Check out this test case:

999000

It needs 999 iterations of your loop, which also include additional operations. There can be a lot of such test cases. I have no idea what limitations N has, what is your time limit and how powerful the testing machine is.

The bottom line is that there is a better algorithm to calculate the next palindrome than looping through all the numbers until you find one.

Let's look at some examples

123 + 8 = 131

[1]2<3> + {8} = 131 # (<3> + {8}) % 10 = [1]

2214 + 8 = 2222

[2]21<4> + {8} = 2222 # (<4> + {8}) % 10 = [2]

2014 + 98 = 2112

[2]01<4> + {8} = 2022  # (<4> + {8}) % 10 = [2]
2[0]<2>2 + {80} = 2102 # (<2> + {8}) % 10 = [0]
2[1]<0>2 + {10} = 2112 # (<0> + {1}) % 10 = [1]

As you can see all you need at each iteration is to just add the number that make the lowest digit equal to the opposite.

In the examples above, I have marked the first digit with square brackets [x] and the 'mirror' digit with angled brackets <x>. You have to add a value {x} to the right digit <x> match the left digit [x]

Solution idea

Iterate the loop until you'll get palindrome and repeat following steps:

  • Find a pair of different digits starting from lower digits (as shown above);
  • Find the additional number that will transform our the pair into equal digits;
  • Remember that number and add it to your original number.

Solution

Here is the solution with my algorithm:

#include <iostream>
#include <vector>
#include <algorithm>

int bin_pow(int a, int n) {
    int res = 1;
    while (n) a & 1 ? (res *= a, n -= 1) : (a *= a, n /= 2);
    return res;
}

class helper : public std::vector<int>
{
    void add(int value) {
        this->counter += value;

        auto rbegin = this->rbegin();
        while (value && rbegin != this->rend()) {
            int current = *rbegin + value % 10;
            *rbegin++ = current % 10;
            value = value / 10 + current / 10;
        }
    }

    int get_additional() const {
        auto begin = this->begin();
        auto rbegin(this->rbegin());

        while (begin != this->end() && *begin == *rbegin)
            ++begin, ++rbegin;

        int value = (*begin - *rbegin + 10) % 10,
            pow = int(begin - this->begin()) + 1;

        return bin_pow(value, pow);
    }
public:
    int counter;

    helper(int number) : std::vector<int>() {
        this->counter = 0;

        while (number) {
            this->push_back(number % 10);
            number /= 10;
        }
        std::reverse(this->begin(), this->end());
    }

    bool is_palindrom() const {
        auto begin = this->begin();
        auto rbegin(this->rbegin());

        while (begin != this->end() && *begin == *rbegin)
            ++begin, ++rbegin;

        return begin == this->end();
    }

    void iterate() {
        this->add(this->get_additional());
    }
};

int main(int argc, char *argv[]) {
    int n, number;
    std::cin >> n;
    while (n--) {
        std::cin >> number;
        helper h(number);
        while (!h.is_palindrom()) {
            h.iterate();
        }
        std::cout << h.counter << std::endl;
    }
}

Source code compiled with clang++, here are some test cases:

$ clang++ codereview.cpp -o codereview --std=c++11 
$ ./codereview 
5
123
8
201
1
193
9
2014
98
999000
999
\$\endgroup\$
  • 2
    \$\begingroup\$ The example solution abuses inheritance. You should use composition ("has a") instead of inheritance ("is a"). Also i believe the solution as presented is more complicated than it needs to be. \$\endgroup\$ – Emily L. Sep 29 '14 at 23:16
  • \$\begingroup\$ @EmilyL., well, it's my code. If you found it complex too much than try to explain why. About grammar: yes I have problems with it. \$\endgroup\$ – outoftime Sep 29 '14 at 23:27
  • 3
    \$\begingroup\$ @outoftime, std:: containers are not meant as base classes. Emily L. is correct: you are abusing inheritance. \$\endgroup\$ – utnapistim Sep 30 '14 at 8:34
  • 2
    \$\begingroup\$ @outoftime, it introduces potential UB in the code, depending on how you allocate/delete instances. It is much easier, in the same way it is much easier to not document your code/do design, or to write monolythic code and use global variables: it works short term/in particular cases, but it is brittle and not really maintainable in the long run. Even if you have good/workable criteria when this works (and respect those) you do not address such criteria in your answer so you are promoting "questionable" coding practices. \$\endgroup\$ – utnapistim Sep 30 '14 at 8:50
  • 1
    \$\begingroup\$ @HongxuChen I didn't say it was too complex. I said it was more complicated than necessary. See my answer. \$\endgroup\$ – Emily L. Sep 30 '14 at 11:05
3
\$\begingroup\$

I would like to give some general suggestions on code improvement and one or two that might actually speed-up the code.

__attribute__:

The __attribute__ qualifier is a Gnu extension. It is OK to write compiler specific code if you have a good reason to do so, but adding the __attribute__((fastcall)) qualifier to the function is hardly doing anything to optimize the code. (Fastcall tells the compiler to pass params in a register if possible). Pushing one integer into the stack will not affect the speed of your code (not in a way you can measure, that's for sure). So I'd remove that.

If you want to give a more significant optimization hint to the compiler, then mark the function as inline instead.

Pass simple types by value:

There is no reason to be passing number by reference, in

bool isPal(const int &number)

Since it is a trivial type, it should be passed by value:

bool isPal(int number)

Unnecessary string copy:

If there is one thing that might be slowing down your code, that would be the copy of buffer into string x. Why don't you just use buffer? Replace x.size() by strlen():

size_t len = strlen(buffer);
for(int i=0, end = len-1; i < end; i++, end--)
    if(buffer[i] != buffer[end])
        return false;

sprintf is unsafe:

sprintf() will happily overflow your buffer if the resulting string is too long. You should avoid using it, since a safer alternative exists, snprintf().

Also, the size of buffer is pretty small (6). Are you sure all of your numbers will never exceed 5 digits? Remember that the last char in the array is need for the null terminator (\0), so you really only have 5, which is quite small.

Clearer name:

isPalindrome() would be a much nicer name. And if you ever want to add a function to your code base that checks to see if one user is a pal of another, you can use isPal() for that ;)

Mixed styles:

C and C++ are two distinct languages, that use different standard libraries. As it stands, your code is a lot more C than C++. So my last suggestion is to chose either one of the two languages and adjust your coding style accordingly.

\$\endgroup\$
  • 2
    \$\begingroup\$ This answer misses the point of the author using the wrong algorithm. \$\endgroup\$ – Emily L. Sep 29 '14 at 23:12
  • \$\begingroup\$ @EmilyL. OK, but I clearly stated at the beginning that I would be giving "general suggestions on code improvement". \$\endgroup\$ – glampert Sep 29 '14 at 23:13
  • 1
    \$\begingroup\$ This forum is about code review, and that includes any aspect of the code, even if mentioning things the OP didn't ask about. \$\endgroup\$ – glampert Sep 29 '14 at 23:14
  • \$\begingroup\$ Do I smell an @EmilyL. answer in the works? \$\endgroup\$ – RubberDuck Sep 29 '14 at 23:26

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.