What is the most time efficient algorithm/code to reverse a very large integer?

Question

I am trying to get the most efficient algorithm to reverse a large integer in Java. E.g. if we have to reverse 301324354432.

Till now I have the below code:

public int reverse(int x) {
        int result = 0;
        while (x != 0)
        {
            int tail = x % 10;
            int newResult = result * 10 + tail;
            if ((newResult - tail) / 10 != result)
            { return 0; }
            result = newResult;
            x = x / 10;
        }
        return result;
    }

What is the correct algorithm to achieve this at best time complexity?

O-notation isn't really helpful here, because if you're talking about int, then n ≤ 11 (and that includes the minus sign). For longs, n ≤ 64. For all practical purposes, you can think of this as O(1). (Yes, it does technically vary on the number of digits -- but there's still a constant upper bound, since there's a constant upper bound on the number of digits. And what's more, that upper bound is small enough that it's actually meaningful.) — yshavit
– yshavit, Commented Jul 20, 2016 at 18:26
How about this : new StringBuilder( String.valueOf(x) ).reverse().toString() ? — SomeDude
– SomeDude, Commented Jul 20, 2016 at 18:34
Your code is already fine, and quite a lot better (more efficient) than most of the answers you're getting involving string manipulation. — Paul Hankin
– Paul Hankin, Commented Jul 21, 2016 at 1:35
I ran a benchmark -- reversing all the ints up to 100 million. George's variant of your code that removes the inner check for overflow runs in 1.3sec, your code in 2sec, and the StringBuffer solution in 6s. I couldn't get the collectors/lambda solution to compile (I think there's something wrong with my java8 installation), but I expect it'll be even slower. — Paul Hankin
– Paul Hankin, Commented Jul 21, 2016 at 1:58

Community · Accepted Answer · 2017-05-23 12:08:18Z

3

An efficient way is to do it as shown below (similar to what you suggested).

public static long reverse(long x) {
    long y = 0;
    while(x > 0) {
        y = y * 10 + x % 10;
        x = x / 10;
    }
    return y;
}

This avoids expensive string conversions, does only one pass through the digits and does not use any memory (except for storing the result).

EDIT

A more efficient way, avoiding division and modulo operations is:

public static long reverse(int _x) {
    long x = _x;
    long y = 0;
    while (x > 0) {
        y = x + (y - ((x * 0x1999999Al) >> 32)) * 10; //y * 10 + x - (x/10) * 10;
        x = ((x * 0x1999999Al) >> 32);
    }
    return y;
}

I also tried replacing multiplication by 10 using bitshift operations (x * 10 = (x << 3) + (x << 1)) but it didn't seem to affect performance. The top answer of this stackoverflow question shows how to divide fast by 10. For completeness, the answer provided states that it can be done as follows (credit to John Källén)

int32_t div10(int32_t dividend) {
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

This approach only allows to reverse an integer number (up to 2^31 - 1). The result is a long, as 2^31 - 1 = 2147483647 and reverse(2147483647) = 7463847412 > 2^31 - 1. A fast way to perform a modulo 10 operation on x is to divide and multiply it by 10, and then subtract that result from x.

edited May 23, 2017 at 12:08

CommunityBot

11 silver badge

answered Jul 20, 2016 at 18:41

George

3,8331 gold badge23 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

sagnikdas Over a year ago

This is awesome. But can you please elaborate what is 0x1999999A? I couldn't figure this. What if, I want to divide x by 5 for some other problem statement; What will be this value?

George Over a year ago

As stated in the linked question, 0x1999999A is approximately equal to 1/10 * 2^32. Multiplying the value by that and then dividing by 2^32 gives the desired output.

Grayson · Accepted Answer · 2016-07-20 18:24:23Z

1

    public int reverse(int x) {
        int result = 0;

        StringBuffer sb = new StringBuffer(0);
        sb.append(x);

        result = Integer.parseInt(sb.reverse().toString());


        return result;
    }

answered Jul 20, 2016 at 18:24

Grayson

7011 gold badge5 silver badges17 bronze badges

Comments

funaquarius24 · Accepted Answer · 2016-07-20 19:01:55Z

0

You can take advantage of Java lambda expression. All you have to do is convert the number to String, use lambda to reverse it and then convert back to int. A little variation of this code can allow the reversal of any number of characters. Here:

public static int reversal(int x) {
      String tmp =  String.valueOf( x );
      String result = Pattern.compile(" +").splitAsStream( tmp ).map(word->new StringBuilder(word).reverse())
      .collect(Collectors.joining(" "));
      return Integer.parseInt( result );
}

answered Jul 20, 2016 at 19:01

funaquarius24

1373 bronze badges

Collectives™ on Stack Overflow

What is the most time efficient algorithm/code to reverse a very large integer?

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related