Gfrktyl

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!

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

}

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.