Why is this solution to Reverse Integer (Leet Code) O((log10(n))?

Question

The problem in question asks to reverse a 32-bit signed integer. Here's the given solution in Java:

    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

​According to the solution's explanation, it's time complexity is O(log10(n)) because there are roughly log10(x) digits in x. Intuitively, there seems to be n-1 iterations of the while loop, where n is the number of digits. (I.E: a 7 digit number requires 6 iterations) However, the solution and given complexity implies that the n is the integer itself and not the number of digits. Can anyone help me gain an intuitive understanding of why the above solution is log10(n) ?

Answer 1

Let's say the x = 123.

int rev = 0;

rev = rev * 10 + x % 10; // rev = 3,   1st iteration.

x = x/10;              // x = 12

rev = rev * 10 + x % 10;  // rev = 3 * 10 + 2 = 32,  2nd iteration

x = x/10;              // x = 1

rev = rev * 10 + x % 10;  // rev = 32 * 10 + 1 = 321, 3rd iteration.

x = 0 so the  loop terminates after 3 iterations for 3 digits.

The conditionals within the loop check to see if the reversed values would exceed what a 32 bit number could hold.

So it is log10(n) exactly for the reason you stated in your question. The log of a number n to a given base is the exponent required to raise the base back to the number n. And the exponent is an approximation of the number of digits in the number.

Based on your comment, it could also have been stated that "For any number n, where m is the the number of digits in n, the time complexity is O(m)."