3
\$\begingroup\$

LeetCode Problem

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

Feedback

Optimized from beta code in the original question here. Based on this LeetCode problem.. I'm trying to come up with a good approach that just math operations to iterate a serious of digits using division, almost treating the int like a stack popping using modulus, and pushing using multiplication.

#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>

class Solution 
{
    public:
        int reverse(int i) {

            if(i > INT_MAX || i < INT_MIN) {
                return 0;
            }                            
            int sign = 1;
            if(i < 0) { 
                sign = -1;
                i = i*sign;
            }

            int reversed = 0;
            int pop = 0;

            while(i > 0) {      
                pop = i % 10;
                reversed = reversed*10 + pop;
                i /= 10;
            }                                

            std::cout << reversed << '\n';

            return reversed*sign;
        }
};

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(1534236469) == 0);
    assert(s.reverse(-2147483412) == -2143847412);
}
\$\endgroup\$
  • 3
    \$\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:41
  • 1
    \$\begingroup\$ That's good feedback CiaPan and I think you raising that as feedback on LeetCode directly would be good next step. \$\endgroup\$ – greg Mar 26 at 23:46
  • 3
    \$\begingroup\$ "but need some help coming up with how to detect and prevent such cases." Asking for advice for code not written yet is off-topic for code review. \$\endgroup\$ – Snowhawk Mar 27 at 3:22
  • 2
    \$\begingroup\$ @greg Sure, but ...I've got no account there, and I don't think I'll create one soon. Feel free to report the ambiguity there yourself. :) This may be not very important in an excercise, but IMHO such omission may be devastating in real software projects. \$\endgroup\$ – CiaPan Mar 27 at 9:12
  • \$\begingroup\$ I've read a few articles and publications and agree on the that point. I want to make sure I'm writing code that is production ready. Okay thanks for the feedback CiaPan, I'll make LeetCode aware of this. \$\endgroup\$ – greg Mar 27 at 20:13
5
\$\begingroup\$

To prevent overflow, you need to check if reversed*10+pop > INT_MAX. But in order to avoid actually overflowing while checking, rearrange the equation to reversed > (INT_MAX-pop)/10;

Actually, I think you should check against -INT_MIN. Which brings up another point. You could use int64_t for reversed. This both ensures it can hold -INT_MIN before fixing the sign, and lets you do the bounds test only once at the end, instead of at each intermediate step.

I would initialize sign with the correct value: int sign = (i<0)?-1:1; i*=sign; . pop can be loop local and doesn't need the 0 initialization.

You should multiply reversed by sign before printing it.

\$\endgroup\$
  • \$\begingroup\$ Also, make the sign const while you initialize. \$\endgroup\$ – Juho Mar 27 at 7:45
  • \$\begingroup\$ int64_t sounds like a great idea. I'm thinking when fixing the sign I will also need to convert the int64_t to int since there will be conflicting return types for my function or is this some automatic conversion that happens behind the scenes? \$\endgroup\$ – greg Mar 27 at 20:33
  • 1
    \$\begingroup\$ Assigning an int64_t to a 32 bit int will automatically truncate the high order bits. If you have already done the limit checking to assure they are zero, then this is no problem. \$\endgroup\$ – AShelly Mar 27 at 21:08
  • 1
    \$\begingroup\$ I see, I compare int64_t to -INT_MIN instead of INT_MAX because -(-2147483648) wil result in a value greater than INT_MAX. \$\endgroup\$ – greg Mar 27 at 21:30
  • \$\begingroup\$ Be careful rearranging arithmetic like that - how does integer truncation affect the correctness of reversed > (INT_MAX-pop)/10? I think that will give false positives. (Of course, your unit tests should stress the boundary conditions...) \$\endgroup\$ – Toby Speight Mar 28 at 8:45
5
\$\begingroup\$

Unused header

We use nothing from <cmath>, so it need not be included.

This should be a function, not a class

Putting all code into a class suggests you have a background in Java or similar.

In C++, we can (and should) use ordinary functions for operations that are mathematically functions. In this case, we have a pure function: it has no state, and should always give the same result for any given input.

If it's part of your program requirements that it must provide this (unhelpfully-named) class, then comment that. I'd recommend that you still write a plain function, and simply provide an adapter to conform to the requirements:

int reverse_decimal_digits(int i);

class Solution 
{
    public:
        int reverse(int i) { return reverse_decimal_digits(i); }
}

Choice of data type

If we're processing a 32-bit integer, then we should be using std::int32_t. Plain int isn't necessarily large enough (it can be any size from 16 bits upwards).

Incorrect test

Given int i, then i > INT_MAX || i < INT_MIN is false by definition. The requirement you quote is (my emphasis):

When the reversed integer overflows, return 0.

Not all integers have a negative

Beware of overflow here:

        if(i < 0) { 
            sign = -1;
            i = i*sign;
        }

On 2s-complement systems, -1 * INT_MIN is undefined.

It turns out that we don't need this step, as in modern C++, the % operator can be used predictably with negative numbers to our advantage (see my modified code, below).

Don't do I/O from a pure function

I guess this is some leftover debugging that should have been removed:

        std::cout << reversed << '\n';

Additional tests

It's good that you've included some unit tests - I wish more people would do that!

Do think about which values to test. Your choice agrees with mine somewhat, but diverges later:

  • 0, 1 and -1 for the three simplest cases.
  • positive and negative two-digit numbers (e.g. 12 and -23).
  • smallest and largest allowable input (INT32_MIN and INT32_MAX).
  • smallest and largest allowable result, and the first overflow in each direction in first and last digits (±1463847412, ±1463847413, ±1563847412).

Don't be tempted to over-test. Tests need to be maintained, too, so try to limit the tests to those that exercise the limits within the implementation.

Minor improvements

The scope of pop can be reduced to within the loop. And perhaps a better name would be digit?

noexcept and constexpr

Can we annotate the function with noexcept and constexpr?

Future

Should the number base be hard-coded to 10? Perhaps there's a use for a reverser that works in arbitrary bases. Certainly, base-16 is convenient for testing.


Modified code

I've used GoogleTest rather than plain C assert(), so as to get better messages when a test fails, but any testing method is fine.

#include <cstdint>

constexpr std::int32_t
reverse_digits(std::int32_t i, int base = 10) noexcept
{
    std::int32_t reversed = 0;
    const bool negative = i < 0;

    while (negative ? i <= -base : i >= base) {
        auto const digit = i % base; // negative if i < 0
        reversed = reversed * base + digit;
        i /= base;
    }

    // final digit may cause overflow
    const bool overflow =
        negative
        ? (reversed < (INT32_MIN - i) / base)
        : (reversed > (INT32_MAX - i) / base);
    if (overflow) {
        return 0;
    }

    return reversed * base + i;
}
#include <gtest/gtest.h>

TEST(Reverse, decimal)
{
    EXPECT_EQ(0, reverse_digits(0));
    EXPECT_EQ(1, reverse_digits(1));
    EXPECT_EQ(-1, reverse_digits(-1));

    EXPECT_EQ(21, reverse_digits(12));
    EXPECT_EQ(-32, reverse_digits(-23));

    EXPECT_EQ(0, reverse_digits(INT32_MIN));
    EXPECT_EQ(0, reverse_digits(INT32_MAX));

    EXPECT_EQ(2147483641, reverse_digits(1463847412));
    EXPECT_EQ(0, reverse_digits(1463847413));
    EXPECT_EQ(0, reverse_digits(1563847412));

    EXPECT_EQ(-2147483641, reverse_digits(-1463847412));
    EXPECT_EQ(0, reverse_digits(-1463847413));
    EXPECT_EQ(0, reverse_digits(-1563847412));
}

TEST(Reverse, hexadecimal)
{
    EXPECT_EQ(0x7ffffff7, reverse_digits(0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(0x10000008, 16));

    EXPECT_EQ(-0x7ffffff7, reverse_digits(-0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(-0x10000008, 16));
}
\$\endgroup\$
  • \$\begingroup\$ Good suggestions, although I don't like testing the sign of i in every loop. It's one of those minor pessimizations that adds up as your system grows. I also think, but haven't proven to myself, that if the initial value fit in an int, then only the very last reversed digit has the possibility for overflow. \$\endgroup\$ – AShelly Mar 28 at 17:49
  • \$\begingroup\$ Good points in your comment; I think they are easy to address. Proving that only the final digit can overflow is a great idea (hint: start with base==2 and it should be obvious), and that saves us a lot of work. I'll edit that in. \$\endgroup\$ – Toby Speight Mar 28 at 17:54

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.