Faster code for leetcode reverse int

Question

This is my solution for the leetcode reverse int question:

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123 Output: 321 Example 2:

Input: -123 Output: -321 Example 3:

Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// Given a 32-bit signed integer, reverse digits of an integer.
    ///
    /// Example 1:
    ///
    /// Input: 123
    /// Output: 321
    /// Example 2:
    ///
    /// Input: -123
    /// Output: -321
    /// Example 3:
    ///
    /// Input: 120
    /// Output: 21
    /// Note:
    /// Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
    /// </summary>
    [TestClass]
    public class UnitTest1
    {
        [TestMethod]
        public void TestMethod1()
        {
            int temp = 1534236469;
            int result = Reverse(temp);
            Assert.AreEqual(0, result);
        }

        [TestMethod]
        public void TestMethod2()
        {
            int temp = 123;
            int result = Reverse(temp);
            Assert.AreEqual(321, result);
        }
        public int Reverse(int x)
        {
            int result = 0;
            bool negative = false;
            if (x < 0)
            {
                negative = true;
                x = -x;
            }

            int prevRevNum = 0;
            while (x != 0)
            {
                int currentDigit = x % 10;
                result = (result * 10) + currentDigit;

                if ((result - currentDigit) / 10 != prevRevNum)
                {
                    return 0;
                }
                prevRevNum = result;
                x = x / 10;
            }

            if (negative)
            {
                return -result;
            }

            return result;
        }
    }
}

This is the output:

Runtime: 52 ms, faster than 62.65% of C# online submissions for Reverse Integer.

Can you please comment on how can I make this code run faster? I guess the modulo and division are the key factors of speed here.

Answer 1

Using a string instead of division / modulo seems to be a few percent faster than the solution from the question:

    public static int Reverse(int x)
    {
        var str = x.ToString();
        int res = 0;
        int multiplier = 1;
        var negative = str[0] == '-';
        for (int i = negative ? 1 : 0; i < str.Length; i++)
        {
            var num = str[i] - 48;
            if (num > 0 || multiplier > 1)
            {
                res += num * multiplier;
                multiplier *= 10;
            }
        }
        return negative ? -res : res;
    }

However, improving the solutions from the question using System.Math.DivRem (as mistertribs suggested in a comment) will be even faster :):

    public static int Reverse(int x)
    {
        var result = 0;
        var negative = x < 0;
        if (negative) x = -x;

        while (x != 0)
        {
            x = Math.DivRem(x, 10, out var rest);
            result = result * 10 + rest;
        }

        return negative ? -result : result;
    }

Answer 2

How fast Math.DivRem is depends on which implementation you're using. Some quick testing shows that .NET Core's approach (which uses subtraction and multiplication instead of a modulo operation) is roughly 30% faster on my system than the .NET Framework implementation (which just uses a modulo and division, like your code does).

---

The overflow check only needs to be performed when processing the last digit (and only when there are 10 digits, but checking digit count isn't free). Moving that out of the loop yields a small performance improvement (about 10% in my tests, depending on input).

It's also slightly faster to compare result against 214748364 (int.MaxValue / 10) and currentDigit against 7 (the last digit of int.MaxValue), instead of subtracting the last digit and dividing by 10.

---

Here's what I ended up with:

public static int Reverse(int x)
{
    var result = 0;
    var isNegative = x < 0;
    if (isNegative)
        x = -x;
    // NOTE: If n == int.MinValue, it'll wrap around to itself,
    //       but it will also skip all of the below code, so the result conveniently remains 0.

    while (x > 9)
    {
        var previousX = x;
        x /= 10;
        var digit = previousX - (x * 10);
        result = (result * 10) + digit;
    }

    if (x > 0)
    {
        // Check for overflow (only necessary for 10-digit input,
        // but checking digit count also takes work so we'll just always check the last digit):
        if (result > 214748364 || (result == 214748364 && x > 7)) // int.MaxValue / 10
            return 0;

        result = result * 10 + x;
    }

    return isNegative ? -result : result;
}

Final note: if you're using tests, why not test edge-cases such as 0, negative numbers and outliers such as int.MinValue and int.MaxValue? Giving test methods meaningful names also helps.