Reversing number without resorting to String in Scala

There is no better way to learn as to try new things without fear of making mistakes.

I wish I’d follow it more often. When I do, I also do my best to let others know so they hopefully let me know where I may have made mistakes.

I’ve recently been exposed to some algorithmic problems and since I’ve never been good at solving them and promised myself to improve I made an attempt to solve one – check whether a number is a palindrome without resorting to using strings.

Here is my solution – a method to reverse a number without using java.lang.String. With the method, when an input number equals the output the number may be a palindrome.

def reverse(n: Integer): Integer = {
  (Stream.continually(n) zip Stream.iterate(10) {_ * 10})
    .takeWhile { case (n,tens) => n * 10 > tens }
    .map { case (n, tens) => n % tens }
    .zipWithIndex
    .map { case (n,i) => n / math.pow(10, i).toInt }
    .reverse
    .zipWithIndex
    .foldLeft(0){ case (res, (n, i)) => res + n * math.pow(10, i).toInt }
}

I humbly ask you to improve the code so in the end I could.

p.s. When a number ends with 0‘s, the reverse method is not sufficient.

Be Sociable, Share!
This entry was posted in Languages.

8 Responses to Reversing number without resorting to String in Scala

  1. Nice. It seems that this incorrectly reverses powers of 10 (i.e., reversing 100, 10000, etc) due to an off by one error. You can fix it by changing the `>` to `>=` on line 3.

    For what it’s worth, here’s my solution: https://gist.github.com/andrewconner/6202431

  2. Vishwa says:

    I do not know Scala, so couldn’t follow the code all that well. But I was tempted to try out in Java. My approach was to try with Stack

    static int reverse(int number)
    {
    Stack numStack = new Stack() ;

    while(number!=0)
    {
    numStack.push(number%10);
    number=number/10;
    }

    int pow=0;
    int reversedNumber=0;
    while(!numStack.empty())
    {
    reversedNumber=reversedNumber+(int)Math.pow(10.0,pow++)*numStack.pop();
    }

    return reversedNumber;
    }

    But to find a palindrome, if we are to use the stack approach, then we would not even have to find the reversed number. We could quit, as soon as we find a non-similar digit

    static boolean isPalindrome(int number)
    {

    int numberCopy=number;
    Stack numStack = new Stack() ;

    while(number!=0)
    {
    numStack.push(number%10);
    number=number/10;
    }
    //now the first digit is at the top of the stack

    while(!numStack.empty())
    {
    int lastDigit=(numberCopy%10);
    numberCopy=numberCopy/10;

    if(lastDigit!=numStack.pop())
    {
    return false;
    }
    }

    return true;
    }

  3. I think that this is one of cases where imperative solution is simply better ;)

    def reverse(n :Int):Int = {
    var up = n
    var down = 0
    while(up > 0) {
    val digit = up % 10
    up = up / 10
    down = 10 * down + digit
    }
    down
    }

    And functional solution should look like this:

    1576.reverseDigits

    where reverseDigits is implemented in given imperative fasion.

    • To be more general I think that algorithmic problems require imperative solutions by definition. Especialy if you need to create solution that is optimized against complexity or memory usage.

      Of course if solution for given problem is created then it can be integrated into declarative language, so it can be used in declarative fashion. But we have to remember that in the end every declarative program is translated into a set of imperative commands that are understandable by a processor.

      Also declarative solution can’t be general as it depends on level of abstraction of a declarative language used, and we can expect that in future languages will allow us to declare domain problems on higher and higher levels of abstraction.

  4. Tomek N. says:

    My tail-recursive solution:

    @tailrec def reverse(n: Int, acc: Int = 0): Int = n match {
    case 0 => acc
    case positive => reverse(n / 10, acc * 10 + n % 10)
    }

    Works for negative numbers and 0 as well. BTW math.pow() is quite slow

    • This is nice recursive solution.

      I was interesed in performance of tail recursion and pattern matching so I’ve runned the performance tests for 3 cases:
      1. With my solution using while loop
      2. Your solution using tail recursion and pattern matching
      3, Your solution with pattern matching changed to if(n==0) {} else {}

      The example results were:
      1 -> 98 ms 314 us 171 ns
      2 -> 76 ms 999 us 987 ns
      3 -> 75 ms 287 us 98 ns

      And those are quite surprising, why tail recursion is faster than while loop?

      To be clear I’ve tried to optimize my while loop so now it is:
      def reverse(n :Int):Int = {
      var up = n
      var down = 0
      while(up != 0) {
      down = 10 * down + up % 10
      up = up / 10
      }
      down
      }

      I’m surpised that recursive solution is faster than while loop, is this becaused JVM optimizations? I’ve tried to run it on JRE 1.6 and 1.7 and the resuls are the same. I’ve changed the order of tests and still the same results.

      Good explanation wanted ;)

  5. Daniel says:

    Clojure one-liner:

    (defn revnum [x] (second (first (drop-while (comp not zero? first) (iterate (fn [[x y]] [(int (/ x 10)) (+ (* y 10) (mod x 10))]) [x 0])))))

  6. And one more solution with Scala’s purely declarative approach:

    def reverse(n: Int): Int = {
    val invertedDigits = Stream.iterate(n)(_ / 10).takeWhile(_ > 0).map(_ % 10)
    invertedDigits.foldLeft(0) {(res, digit) => res * 10 + digit}
    }

    It is 10 times slower than imperative approach ;) but I hope it’s quite efficient as declarative solution.

Leave a Reply

%d bloggers like this: