Kodemonk

PALIN – The Next Palindrome

Problem:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Read More Here


Hint: Be aware of corner cases like “000”,”9999″ etc. First try to find the different cases are possible.  Start comparing the middle elements.


Code:


#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

bool all9(string &str){
    
    for(int i =0; i < str.size(); i++){
        if(str[i]!='9')
            return false;
    }
    cout<<"1";
    for(int i=1; i<str.size(); i++)
        cout<<"0";
    cout<<"1"<<endl; return true; } void helper(string &str){ int length = str.size(); int i = ceil(length/2.0) -1,j=floor(length/2.0); int element, carry = 1 ; while(i>=0){
            element = str[i]-'0';
            str[i] = (element+carry)%10 + '0';
            str[j++] = str[i--];
            
            if(element<9) carry =0 ; } } int main(){ lli T; cin>>T;
    string str;
    
    while(T--){
        cin>>str;
        if(all9(str))
            continue;
        int length = str.size();
        int i = ceil(length/2.0) -1,j=floor(length/2.0);
        
        while(i>=0 && str[i]==str[j])
            i--,j++;
            
        if(i<0 || str[i] < str[j]) helper(str); else{ i = ceil(length/2.0) -1,j=floor(length/2.0); while(i>=0)
                str[j++]=str[i--];
        }
        cout<<str<<endl;
    }
    return 0;
}


Explanation: As discussed in the hint we first handle the case when all characters are 9, in program that are handled by function all9. Then we start comparing the left half and right half start from middle element/elements. After that we find the first mismatch of characters if possible(Not possible if number is already palindrome). There are two possibilities when mismatched element of left half is greater, in this case we just have to copy left half into right half. In another case when mismatched element of right half is greater, in this case we increment the middle element by 1 and propagate the carry towards left end and copy left half to right half. This things in code is done by  helper function.

Want to improve your coding skill in c++? Try this book C++: The Complete Reference, 4th Edition

Share This:

Next Post

Previous Post

© 2017 Kodemonk

Theme by Anders Norén