4
\$\begingroup\$

Problem

Reverse digits of a 32-bit signed integer. When the reversed integer overflows return 0. Optimized code here.

Feedback

I'm looking for any ways I can optimize this with modern C++ features overall. I hope my use of const-correctness, exception handling, and assertions is implemented well here, please let me know. Is there any way I can use byte operations to reverse the int and keep track of the sign possibly?

Based on the submission feedback from LeetCode, is it safe to say that the time complexity is \$O(n)\$ and space complexity is \$O(n)\$? If I can reduce the complexity in anyway would love to know!

enter image description here

#include <cassert>
#include <climits>
#include <stdexcept>
#include <string>

class Solution 
{
    public:
        int reverse(int i) {
            bool is_signed = false;
            if(i < 0) { is_signed = true; }

            auto i_string = std::to_string(i);

            std::string reversed = "";
            while(!i_string.empty()) {
                reversed.push_back(i_string.back());        
                i_string.pop_back();
            }

            try {
                i = std::stoi(reversed);
            } catch (const std::out_of_range& e) {
                return 0;
            }

            if(is_signed) { i *= -1; }

            return i;
        }
};

int main()
{
    Solution s;
    assert(s.reverse(1) == 1);
    assert(s.reverse(0) == 0);
    assert(s.reverse(123) == 321);
    assert(s.reverse(120) == 21);
    assert(s.reverse(-123) == -321);
    assert(s.reverse(1207) == 7021);    
    assert(s.reverse(INT_MAX) == 0);
    assert(s.reverse(INT_MIN) == 0);
}
\$\endgroup\$
  • \$\begingroup\$ This leetcode.com/problems/reverse-integer ? \$\endgroup\$ – Martin R Mar 23 at 18:39
  • \$\begingroup\$ Yes that's the one \$\endgroup\$ – greg Mar 23 at 19:03
  • \$\begingroup\$ The problem is ill-posed. If 'the' reverse of 120 is 21, how can you know whether 'the' reverse of 21 should be 120 or 12? What makes 'the' reverse of 1 number 1 and not 10000? How can you tell your code solves the problem if the correct solution is not defined? \$\endgroup\$ – CiaPan Mar 26 at 23:42
8
\$\begingroup\$

General comments

  • There is no reason to use a class. Instead, the functionality should be made into a free function.

  • Your code is overly complicated. There is no reason to make new string from which you erase characters one-by-one. Instead, you can convert the input integer to a string and use a standard function to reverse that.

  • Also, pay attention to const correctness. This protects from unintended mistakes and helps the compiler optimize more.

I would simplify your function to just:

int reverse(int i) 
{
    try
    {
        auto reversed{ std::to_string(i) };
        std::reverse(reversed.begin(), reversed.end());

        const auto result{ std::stoi(reversed) };
        return i < 0 ? -1 * result : result;
    }
    catch (const std::out_of_range& e) 
    {
        return 0;
    }
}

Further comments

  • If you want to have a fast solution, you should avoid std::string altogether. This you can do by "iterating" through the digits using arithmetic operations (division and modulus), as in (using std::string to only show you what is happening):

    int x = 1234;
    std::string s;
    
    while (x > 0)
    {
        s.push_back('0' + (x % 10));
        x /= 10;
    }
    
    std::cout << s << "\n"; // Prints 4321
    

    I will let you take it from here to use these ideas to make your program even faster.

  • Regarding your theoretical question concerning complexity, if we assume that the input is treated as a string of n characters, there is \$\Omega(n)\$ lower bound by a trivial adversary argument. Basically, if you don't spend at least n time, you can't read the whole of the input, and then you cannot guarantee correct output on every instance.

\$\endgroup\$
  • \$\begingroup\$ Trying the digit iteration now, great concept that I'm adding to my toolbox. Fantastic feedback. \$\endgroup\$ – greg Mar 25 at 1:59
  • \$\begingroup\$ if you'd like to see the optimized version I've edited my post \$\endgroup\$ – greg Mar 25 at 20:11
  • 1
    \$\begingroup\$ @greg I'd be happy to comment on that as well, but you shouldn't change your code after you've received an answer. Instead, you should post it as a separate question. \$\endgroup\$ – Juho Mar 25 at 21:08
  • 1
    \$\begingroup\$ @esote Great, thanks for the edits! I know how to use Latex now on this site too :-) \$\endgroup\$ – Juho Mar 25 at 21:09
  • \$\begingroup\$ Updated the code here codereview.stackexchange.com/questions/216300/… learning math operations to pop and push digits has been very valuable in optimizing this \$\endgroup\$ – greg Mar 26 at 23:15

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.