A better algorithm to find the next palindrome in Scala

Question

Here is the question:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input: The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output: For each K, output the smallest palindrome larger than K. Example

Input:

2 808 2133

Output:

818 2222

And my Scala code:

object Pro_5 {

  // find the next palindrome larger than K
  def findPalindrome(input: String) = {
    // start from (k + 1)
    val tmp = (BigInt(input) + 1).toString

    val length = tmp.length
    val mid = length / 2

    val left = tmp.substring(0, length >> 1)
    val right = tmp.substring(length >> 1, length)

    // whether continue for loop
    var flag = true
    // half of the result
    var res = ""

    for (i <- 0 until mid if flag) {
      if (left(i) > right(mid - 1)) {
        res = left
        flag = false
      } else if (left(i) < right(mid - 1)) {
        res = (BigInt(left) + 1).toString()
        flag = false
      }
    }

    if (length % 2 == 0) {
      res + res.reverse
    } else {
      res + tmp(mid) + res.reverse
    }

  }

  // get K
  def getInput(times: Int) = {
    for (time <- 0 until times) yield readLine()
  }

  def main(args: Array[String]) {
    // get compute times
    val times = readInt()
    getInput(times).map(findPalindrome(_)).foreach(println)
  }

}

I learn something from Mark Peters 's answer

But when I run it in the SPOJ, i still got a time limit exceeding error.

Can you help me to improve the algorithm?

Any answer will be welcom...

it fails the very first test actually `findPalindrome("808")` ---> "808" — harshtuna, Jun 20 '15 at 14:58

score 1 · Accepted Answer · edited May 23 '17 at 11:50

1

A good algorithm is already explained in Mark Peters's answer indeed

so it's just a matter of correct implementation. Here's a hint how to improve the code, make it less java and support odd digit count

def split(s: String) = {
  val mid = (s.length + 1) / 2
  val left = s.substring(0, mid)
  val right = s.substring(s.length - mid, s.length)
  (left, right)
}

//right string should be reversed
@tailrec
def compareFromIndex(left: String, right: String, i: Int): String = {
  if (i < 0) left
  if (left(i) > right(i)) left
  else if (left(i) < right(i)) (BigInt(left) + 1).toString()
  else compareFromIndex(left, right, i - 1)
}

val half = compareFromIndex(left, right.reverse, left.length - 1)

This is almost complete implementation :) Just pas correct input to split function. And make full palindrome from the calculated "half". Good luck!

edited May 23 '17 at 11:50

Community

1
1

answered Jun 20 '15 at 15:58

harshtuna

757
5
14

@hashtuna This only works for numbers of even length. When the number is odd you have to increment the digit in the middle if the right character is greather than the left character. – Peter Neyens Jun 20 '15 at 16:14
@PeterNeyens it does work for odd-figit-count numbers: `split("809")` -> ("80", "09"). In my solution the middle char is included to both left and right. Less exceptional cases to handle. Then `compareFromIndex("80", "90", 1)` -> "81". The last step would be "81" -> "818". Voila! :) – harshtuna Jun 20 '15 at 16:22
1

@hashtuna You are right. You just have to handle the odd case when turning the half into the palindrome. – Peter Neyens Jun 20 '15 at 16:40

A better algorithm to find the next palindrome in Scala

1 Answers1