Saturday, 12 April 2014

Next palindrome of a given number

Given a number , find out the next palindrome. For example

if n is 179, next palindrome is 181
if n is 456, next palindrome is 464
if n is 497, next palindrome is 505

If the given no is palindrome, return the same number.

Solution:
1.Store all digits into an array in the same order as the input number.
2.Check the first digit with last digit(1's pos),
3.if they are same , do nothing
4. if first no is greater than the last number, then replace the last number(1's pos) with first number and check the resultant is palindrome
5. if first no is less than the last no(1's pos) then replace the last number with first and increment the next to last no(10's pos) by 1.If you get more than 10 when you add 1 , then carry forward to 100's pos digit.continue this till you reach the first number or you get no carry.

bool isPalin(int a[],int dig)
{
    int i=0;
    int j=dig;
    while(i<j)
    {
    if(a[i]!=a[j-1])
        return false;
    i++;
    j--;
    }
    cout<<"Next palindrome no :";
    for(int i=0;i<dig;i++)
    {
        cout<<a[i];
    }
    return true;
}

void reverse(int *a,int digits)
{
    int j=digits;
    for(int i=0;i<j;i++,j--)
    {
        int t=a[i];
        a[i]=a[j-1];
        a[j-1]=t;
    }
    cout<<"input no :"<<endl;
    for(int i=0;i<digits;i++)
    {
        cout<<a[i];
    }
}

void find(int a[],int dig)
{
    /*for(int i=0;i<dig;i++)
    {
        cout<<a[i];
    }*/
    int j=dig;
    j--;
    for(int i=0;i<=j;i++,j--)
    {
        if(a[i]==a[j])
        {
            //do nothing
        }
        else
            if(a[i]>a[j])
            {
                a[j]=a[i];
                if(isPalin(a,dig))
                break;
            }
            else
            {
                a[j]=a[i];
                int k=j;
                int l=1;
                int t=0;
                do
                {
                    t=a[k-l] +1;
                    a[j-l] = t%10;
                    t = t / 10;
                    l++;
                }while(t>0);
            if(isPalin(a,dig))
                break;
            else
                find(a,dig);
            }

    }
}
void nextpalin(int n)
{
    int *a=new int[10];
    int dig;
    for( dig=0;n>0;dig++)
    {
        a[dig]=n%10;
        n=n/10;
    }
    reverse(a,dig);
    find(a,dig);
}

No comments:

Post a Comment

AWS Data Pipeline Services

https://www.youtube.com/watch?v=tykcCf-Zz1M