Skip to main content

Finding next smallest Palindrome Number

A Palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward for example '123321' or 'racecar'.
Given a number inorder to find the next smallest palindrome we need to consider the following cases:
  • Case 1 : if the number is less than 10 if yes then the smallest palindrome is 11.
  • Case 2 : if the number contains all digits to be 9 eg. 9 , 99 , 999 , 9999 in such case the next smallest palindrome is 11 , 101 , 1001 , 10001 as we can see it contains n+1 digits with n-1 0's between two 1's.
  • Case 3: considering if the entered number is already a palindrome then we have 2 cases to deal with 
    1. If it does not contain a 9 in its middle digits for eg 1771 or 171 in such cases it is very easy to find the next smallest palindrome you only need to add one to the middle digits so the answer for above cases is 1881 or 181.
    2. For the Second case if it contains one in the middle digits for eg. 1991 or 17971 in this case if we add 1 to 9 it becomes 10 hence to solve this we replace 9 by 0 and add on to the digits that are besides 9 so the answer will be 2002 and 13031. also if it has more than two 9's in the middle we just keep replacing them with 0's and add on to the digits besides then eg. 139999931 the answer is 140000041
  • Case 4 : if the number is not already a palindrome then we again have 2 cases to deal with let us consider we have number 18921 so we take 2 variables i and j pointing to the middle elements that are unequal (here i points 8 and j points 2 i.e the elements besides mid element in case of odd length). then we check for the following cases : 
    1. Sub-case 1: if the ith element is greater than the jth element if yes then we simple copy the left hand side to the right hand side in this case 18921 replace 21 with 81 from the left hand side so answer is 18981.
    2. Sub-case 2 : let us consider another number 12691 in this case ith element is less than the jth element hence copying left side to the right does not work hence we add one to all the digits between ith and jth element and then copy left side to the right side so the answer is 12721.

C++ Program

Sample input and output to check the program



Labels:

Comments

Post a Comment

Popular posts from this blog

Home Page

List of All Programs The Following is the List of all the programs on my Blog Math Programs Square Root of a number using Babylonian Method Finding The Next Smallest Palindrome Finding the Armstrong Numbers Factorial of a number GCD using Euclid's Algorithm Check if a number is Fibonacci Number or not LCM of 2 numbers Trailing Zeros in factorial of a number Sorting Algorithms Bubble Sort Algorithm Selection Sort Algorithm Insertion Sort Algorithm Shell Sort Algorithm Counting Sort Algorithm Linked List Programs Simple Singly Linked List Linked List in C++ Linked List in Python Linked List in Java Doubly Linked List Finding Kth element from the end of Linked List Delete a node from Linked List Delete Kth element from the end of Linked List Rotate Linked List in an Anti-clockwise direction Reversing first K nodes of a Linked List Binary Search Tree Left View of Binary Tree Righ
4 comments
Read more

Hashing with Quadratic Probing

Hashing is a technique used for storing , searching and removing elements in almost constant time. Hashing is done with help of a hash function that generates index for a given input, then this index can be used to search the elements, store an element, or remove that element from that index. A hash function is a function that is used to map the data elements to their position in the data structure used. For example if we use an array to store the integer elements then the hash function will generate position for each element so that searching, storing and removing operation on the array can be done in constant time that is independent of the number of elements in the array. For better look at the example below. now we face a problem if for 2 numbers same position is generated example consider elements 1 and 14 1 % 13 = 1 14 % 13 = 1 so when we get 1 we store it at the first position, but when we get 14 we see that the position 1 is already taken, this is a case of colli
Post a Comment
Read more

Infix to Prefix conversion using Stack

This post is about conversion of Infix expression to Prefix conversion. For this conversion we take help of stack data structure, we need to push and pop the operators in and out of the stack. Infix expressions are the expressions that we normally use, eg. 5+6-7; a+b*c etc. Prefix expressions are the expressions in which the 2 operands are preceded by the operator eg. -+56 7 , +a*bc etc. This method is very similar to the method that we used to convert Infix to Postfix but the only difference is that here we need to reverse the input string before conversion and then reverse the final output string before displaying it. NOTE: This changes one thing that is instead of encountering the opening bracket we now first encounter the closing bracket and we make changes accordingly in our code. So, to convert an infix expression to a prefix expression we follow the below steps (we have 2 string, 1st is the input infix expression string 2nd is the output string which is empty initially)
Post a Comment
Read more