The Next Palindrome: Is my code efficient?

Question

I was trying to solve the Next Palindrome problem listed in SPOJ in Ruby language. Please find the problem statement here. Though i came up with the below solution, i could not get the execution time below 1.4s even after tweaking this code numerous times. Where can this code be optimized in terms of memory and execution time or is there a better approach than the solution i came up with?

def next_palindrome 
  number = gets.chomp
  len = number.length
  if len == 1
    return "11\n" if number == "9"
    return number.next!<<"\n" 
  end
  if len.even?
    f = len/2   
    return number[0..f-1]<<number[0..f-1].reverse<<"\n" if number[0..f-1]>number[f..-1]
    number = number[0..f-1].next!
    return number<<number[0..f-1].reverse<<"\n"
  else
    f = (len-1)/2-1         
    return number[0..f+1]<<number[0..f].reverse<<"\n" if number[0..f]>number[f+2..-1] 
    number = number[0..f+1].next!       
    return number<<number[0..f].reverse<<"\n"
  end
end

def input
  gets.chomp.to_i.times {print next_palindrome}      
end

input

Answer 1

Cache cache cache! :) All those substrings you take should be stored in variables, rather than using the expensive substring methods. Furthermore, comparing strings can also be expensive. When you store the substring in a variable, you could parse the integer and keep it for comparisons later.

Advanced:

Since you never need to look at the last half number (if it's a palindrome it must be the reverse of the first digits), you can just store two variables: big_half and small_half. for even-digit numbers, they will be equal, but for odd-digit numbers big_half will have the middle digit. This makes creating a that is adjacent to the number (either just smaller or just larger) as simple as big_half + small_half.reverse. If a test shows it's the smaller one, increment big_half and generate a new small_half from it, then add together as above.

Answer 2

I think you are over-complicating things here. I think there's two solutions to your problem.

• Comparing two halves of the string
• Recursively comparing chars[i] with chars[n-1-i], where n is the size

Mark did explained our first option, so let me explain the second. We already know that if our number is a palindrome, the first char will equals the last one, the second with equals the one before the last, etc...

As an example, let's start with a first number of 808.

# our number
k = "808"

# let's continue until we break!
while i = k.next! do

  # what is the size of our string?
  size = i.size

  # the next loop returns nil if two chars weren't equal
  # if it doesn't return nil, that means we have a palindrome! We can break
  break if (size / 2).ceil.times do |j|

    # Let's compare the first and the last chars.
    # If they aren't equal, we break (return nil).
    break unless i[j] == i[size - (j + 1)]
  end
end

puts i