6

in c++ what will be the fastest logic to find next palindrome of a given 15 digit number? for example what will be the next palindrome of: 134567329807541 ?

5
  • 1
    +1 very interesting question, IMO
    – Edan Maor
    Oct 4, 2009 at 9:48
  • 1
    What does 'the next palindrome of x' mean?
    – Joren
    Oct 4, 2009 at 10:13
  • 1
    A palindrome is something that reads the same backwards and forwards (as you hopefully know from Monty Python's parrot sketch!), so I'd guess "the next palindrome of x" is the first number >= x which, in base 10, reads the same backwards and forwards.
    – jalf
    Oct 4, 2009 at 10:39
  • 1
    You have got a number of answers already. I just want to point out that, since this has a C++ tag, std::string (which you should use) has a lot of member functions to manipulate its contents. Unfortunately, for historical reasons, some of them work with indexes, some work with iterators, many (but not all) have versions for both, many (but not all) have alternative algorithms in the <algorithm> header. A good way to in-place reverse a sequence supplying random-access iterators is using std::reverse(), a good way to compare two arbitrary sequences is std::equal().
    – sbi
    Oct 4, 2009 at 12:00
  • I am wondering: does 'next' means that if you already have a palindrom you should get the following one or are you content with it? Oct 4, 2009 at 12:21

5 Answers 5

16
  • Split the number into three parts, head, mid, tail

    1345673 2 9807541

  • 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
  • result := head mid reverse(head).

    1345673 3 reverse(1345673) => 134567333765431

5
  • and what if reverse(head)>tail ??
    – Vaibhav
    Oct 4, 2009 at 11:30
  • 4
    That's left as an exercise :-)
    – starblue
    Oct 4, 2009 at 11:36
  • 1
    if reverse(head)>tail you continue with "result:=..."
    – hjhill
    Oct 4, 2009 at 11:37
  • what if you have even number of digits ? Jun 24, 2013 at 18:11
  • @CosminVacaroiu 15 is not an even number. Jun 25, 2013 at 9:33
3

I believe it's like this

  1. Split the number into three parts 1345673 2 9807541
  2. Flip the last one 1457089
  3. If it's larger than the first part (it is in this case)
    • firstpart++
    • middlepart = 0
  4. flip first part and replace last part.
5
  • That’s the same I came up with, so +1. Oct 4, 2009 at 9:58
  • 9
    There's a little bug here, I think... For example, take a look at what happens to the input "13 5 09" (using a five-digit number for convenience). The next palindrome is "13 5 31", but the algorithm gives "14 0 41". To fix this, step 2 should be: Flip the first part, and step 3 should be: If it's smaller than the last part.
    – Martin B
    Oct 4, 2009 at 10:02
  • 2
    Another edge case to consider is if the input is the last 15-digit palindrome ("999999999999999").
    – Martin B
    Oct 4, 2009 at 10:06
  • 5
    There are so many bugs that I doubt your algorithm is even useful. 1. Flip the first part, and use as last part. If the result is larger than the original number, you're don. 2. If it's smaller, increment the middle part. 3. If the middle part was 9 (now 10), make it 0 and increment first part.
    – bart
    Oct 4, 2009 at 10:25
  • Oh, I forgot: in the last case, flip the incremented first part and use that as the new last part.
    – bart
    Oct 4, 2009 at 10:30
1

I am not about to implement anything, but I imagine the logic would be:

  1. Split the number at the middle of the string: X being the left part and Y being the right part.
  2. Let X' = { X + 1 if reverse(X) < Y; X otherwise }
  3. The result is then concat(X',reverse(X'));

If the length is uneven, you need to treat the middle digit separately. But that is quite trivial.

0

I think the following algo should also work .. It is easier to implement also

  i) Divide the given nos into three parts  HEAD MID TAIL 
  ii) Add 1 to number HEAD MID
          (in case of carry, follow basic addition rules)   
  iii) reverse the new HEAD(store it in HEAD_REV)
  iv) required ans is:-  'new HEAD' MID  HEAD_REV

Hoping that following example will help in better understanding of the algo

let nos be:- 23469 9 12367

       So HEAD -> 23469   MID -> 9   TAIL --> 12367

       step 2:-   23469 9 +1 = 23470 0 
              (now HEAD -> 23470 MID -> 0 HEAD_REV -> 07432 )

required Ans:-
23470 0 07432

Plz do infrom me if there exist any flaw in this procedure

2
  • yes there is flaw!! ex:- 34512 head- 34 mid - 5 tail- 12 your answer 35553 but a smaller pallindrome and correct answer 34543!!
    – Shivendra
    Dec 1, 2013 at 9:15
  • correct algo should be, calculate the head mid and tail... if head>tail answer- head mid reverse-head if head<=tail answer- head+1 mid reverse-head+1
    – Shivendra
    Dec 1, 2013 at 9:19
0
Split the number into three parts head, mid and tail

if reverse(head)>tail 
result := head mid reverse(head)
else if reverse(head)= tail && mid<9 
    mid++
    result := head mid tail
else 
mid =0
head++
result := head mid reverse(head)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.