Saturday, July 13, 2013

If given a 15 digit number whats the best way to find the next palindrome?

If given a 15 digit number what is the best way to find the next palindrome? for example what will be the next palindrome of: 134567329807541?

Algorithm:

Step1: Split the number into three parts, head, mid, tail

number = 134567329807541
count = no. of characters = 15
head = number.substring(0, count / 2) = number.substring(0,7) = 1345673
mid = number.substring((count / 2), (count / 2) + 1) = number.substring(7,8) = 2
tail = number.substring((count / 2) + 1) = number.substring(8) = 9807541

head   mid        tail
1345673     2                   9807541
Step2: Reverse head and compare it to tail 3765431
  • If reverse(head) <= tail ( if they are equal the initial input is a palindrome, and you want the next )
    • If mid < 9, increment mid
    • Else increment head part and set mid := 0
     
reverseHead = rev(head) = 3765431
if(reverseHead == tail) {
           if (m <= 9) {
                m++;
            } else {
                m = 0;
                h = h + 1;
            }
}

Step3: Result is head mid reverse(head). 
result = head + mid + rev(head)
           = 1345673+ 3 + reverseHead 
           = 134567333765431

0 comments: