Reverse int within the 32-bit signed integer range

Question

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

• Martin R: This leetcode.com/problems/reverse-integer ?
• greg: Yes that's the one
• CiaPan: 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?

Answer 1

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.

• greg: Trying the digit iteration now, great concept that I'm adding to my toolbox. Fantastic feedback.
• greg: if you'd like to see the optimized version I've edited my post
• Juho: @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.
• Juho: @esote Great, thanks for the edits! I know how to use Latex now on this site too :-)
• greg: Updated the code here codereview.stackexchange.com/questions/216300/… learning math operations to pop and push digits has been very valuable in optimizing this