Friday, 2 October 2015

PALIN - The Next Palindrome

See on SPOJ


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.

 

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

 

Output

For each K, output the smallest palindrome larger than K.

 

Example

Input:
2
808
2133
Output:
818
2222

Solution- Trace from Middle. O(n)

This solution is an approach to avoid recursion.
Take the input as an array of characters (or String). Then there will be 2 big cases.
  • The input number is a palindrome and has all 9s. For example “9 9 9″. The output should be “1 0 0 1″. for this, we will just output the string of length 1 greater than the previous with 1 at ends and 0 in middle.
  • Other cases. say 2133
    1. Split it into the left half and right half ("21", "33");
    2. Compare the last digit in the left half and the first digit in the right half.
      a. If the right is greater than the left, increment the left and stop. ("22")
      b. If the right is less than the left, stop.
      c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
    3. Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

Applied to a more complicated  Even length number:
1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

Applied to a more complicated ODD length number:
1.    12345678987654322
2.    12345678 9 87654322
3.    12345678 9 87654322
             ^   ^         equal
3.    12345678 9 87654322
            ^     ^        equal
3.    12345678 9 87654322
           ^       ^       equal
3.    12345678 9 87654322
          ^         ^      equal
3.    12345678 9 87654322
         ^           ^     equal
3.    12345678 9 87654322
        ^             ^    equal
3.    12345678 9 87654322
       ^               ^   equal
3.    12345678 9 87654322
      ^                 ^  greater than, so increment the middle,
                           but middle is max (9) here so make it zero 
                           and increment the next closer digits on both sides(8)
 
 3.    12345679 0 97654321 and make second half same.

4.    12345679097654321  answer
 


Implementation in C++. Time taken is 0.08 sec.


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//next palindrome



#include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
     #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }
    

    int all_nine(string str)  //check if all digits are '9' 
    {
        for(int i=0;i<str.length();i++)
        {
            if(str[i]!='9')
                return 0;
        }
        return 1;
    }
     
    int main()
    {
        string str;
        int t;
        s(t);
        
        while(t--){
        cin>>str;
        int i,j,num;
        char ans[str.length()+3];
        int n=str.length();
        
        if(all_nine(str))
        {                       //if all 9
            ans[0]='1';
            for(i=0;i<n;i++)   
            {
                ans[i+1]='0';
            }
            ans[n]='1';
            ans[n+1]='\0';
            cout<<ans<<endl;
        }
        
        else
        {
            i=n/2;
            j=i;
     
            if(n%2==0)  
            i=i-1;
     
            while(i>=0 && str[i]==str[j])
            {                   //checking for equal from middle
                                // <---i    j--->           
                i--;
                j++;
            }
     
            if(i<0 || str[i]<str[j])
            {                   //not equal or string is palindroic(i<0)
                i=n/2;
                j=i;
                if(n%2==0)
                    i=i-1;
            int carry=1;
            while(i>=0)
            {
                num=((str[i]-'0')+carry);
                carry=num/10;
                str[i]=(num%10)+'0';
                str[j]=str[i];
                i--;
                j++;
            }
            }
            else
            {
                while(i>=0)     //making second half same.
                    {
                        str[j]=str[i];
                        i--;
                        j++;
                    }
            }
            cout<<str<<endl;
        }
        
        }
        return 0;
    }

Posted by at
Labels: , , , , ,

14 comments:

  1. Unknown27 October 2017 at 05:55

    Good explanation

    ReplyDelete
  2. Unknown2 June 2019 at 23:08

    #include
    #include
    using namespace std;

    bool allNine(string s){
    for(int i = 0 ; i < s.size() ; i++){
    if(s[i]!='9')
    return false;
    }
    return true;
    }

    int isNotSmaller(string a, string b) {
    int n = a.length();
    char ch[n + 1];
    strcpy(ch, a.c_str());

    int n2 = b.length();
    char ch2[n2 + 1];
    strcpy(ch2, b.c_str());

    return strcmp(ch, ch2);


    }



    int main(){
    string s,temp;
    int t; cin>>t;
    while(t--){
    cin>>s;

    if(allNine(s)){
    for(int i=0;i rmid)? lmid : rmid ;
    lmid = a;
    rmid = a;

    s[mid-1] = a;
    s[mid] = a;
    }



    for(int i = 0 ; i < mid-1 ; i++){
    s[s.size() - i - 1] = s[i];
    }

    if(isNotSmaller(s,temp) <= 0){
    int mid1 = s.size()/2;
    int mid2 = mid1-1;
    if(s[mid2] != '9'){
    //cout<= 0 ; i--){
    if(s[i] != '9'){
    break;
    }
    lastNine = i;
    }
    if(lastNine == mid2){
    //no following nine
    s[mid2-1]+=1;
    s[mid1+1] = s[mid2-1];
    }else{
    s[lastNine-1]+=1;
    s[s.size()-1-lastNine] = s[lastNine-1];
    for(int i = lastNine; i < mid1 ; i++){
    s[i]='0';
    s[s.size()-1-i] =s[i];
    }

    }

    }
    }


    }//even length
    else{
    temp = s;
    int mid = s.size()/2;

    for(int i = 0 ; i < mid ; i++)
    s[s.size() - 1 - i] = s[i];

    if(isNotSmaller(s,temp)<=0){
    int mid = (s.size()-1)/2;
    if(s[mid] != '9'){
    s[mid]+=1;
    }else{
    int lastNine = mid;
    s[mid]='0';
    //cout<<"SHOULD MID BE 0"<= 0 ; i--){
    if(s[i] != '9'){
    break;
    }
    lastNine = i;
    }
    //cout<<"SHOULD MID BE 000 "<<s<<endl;
    s[lastNine-1]+=1;
    s[s.size()-1-lastNine-1] = s[lastNine-1];
    s[mid] = '0';
    //cout<<"SHOULD MID BE 0 "<<s<<endl;
    for(int i = lastNine; i < mid; i++){
    s[i]='0';
    s[s.size()-1-i] =s[i];
    }
    //cout<<"SHOULD MID BE 000 "<<s<<endl;

    }
    }


    }//odd length



    for(int i = 0 ; i < s.size()/2 ; i++)
    s[s.size()-1-i] = s[i];

    cout<<s<<endl;



    }


    }




    CAn you please tell which test case I am failing

    ReplyDelete
  3. Himanshu24 September 2019 at 12:32

    Excellent explanation!

    ReplyDelete
  4. Unknown11 April 2020 at 12:35

    I really liked the approach.

    ReplyDelete
  5. Unknown12 May 2020 at 00:50

    I have tried this, but showing time limit exceeded.
    #include
    //#define _OPEN_SYS_ITOA_EXT
    //#include
    //#include
    using namespace std;
    bool palin(int num )
    {
    string s ;
    s = to_string(num) ;
    int l = 0;
    int r = s.length() - 1;
    while(l < r)
    {
    if(s[l] != s[r])
    return false ;
    l++ ;
    r--;
    }
    return true ;
    }
    int main() {

    // your code here

    int t ;
    cin >> t ;
    while(t--)
    {
    string s ;
    cin >> s;
    //string s = to_string(num) ;
    int l = 0;
    int r = s.length() -1;
    while( l <= r)
    {
    if(s[l] == s[r] && s[r] == '9')
    {
    l++;
    r--;
    }
    else
    break;
    }
    if(l > r)
    {
    string ans1 ;
    char one = '1' ;
    ans1.push_back(one) ;
    char zero = '0' ;
    for(int i = 0; i < s.length() -1;i++)
    ans1.push_back(zero) ;
    ans1.push_back(one) ;

    cout << ans1 ;
    if(t > 0)
    cout << endl ;
    continue ;

    }
    string ans = s ;
    l = 0;
    r = s.length() - 1;
    // cout << ans << endl ;
    while(l < r)
    {
    ans[r] = s[l] ;
    r--;
    l++ ;
    }
    //cout << ans << endl ;
    int n = s.length() ;
    if(ans <= s)
    {

    if(n%2 != 0 )
    {
    int h = n/2 ;
    if(ans[h] != '9')
    {
    int k = ans[h] - '0' ;
    k++ ;
    ans[h] = k + '0' ;
    }
    else
    ans[h] = '0' ;
    }
    l = n/2 - 1;
    if(n%2 == 0 )
    r = n/2 ;
    else
    r = n/2 + 1;
    while( l != 0 && ans <= s)
    {
    if(ans[l] != '9')
    {
    int k = ans[l] - '0' ;
    k++ ;
    ans[r] = ans[l] = k + '0' ;
    }
    else
    ans[r] = ans[l] = '0' ;
    l--;
    r++ ;

    }
    }

    cout << ans;
    if(t > 0 )
    cout << endl ;




    }
    return 0;
    }

    ReplyDelete
    Replies
    1. Pradeep3 July 2020 at 22:18

      please provide Ideone Link with test cases.

      Delete
  6. Pradeep3 July 2020 at 22:18

    This comment has been removed by the author.

    ReplyDelete
  7. Unknown23 July 2020 at 18:54

    def chck99(x):
    x=str(x)
    for i in x:
    if i!='9':
    return False
    return True
    for z in range(int(input())):
    k=str(input())
    if chck99(k):
    print ('1'+('0'*(len(k)-1))+'1')
    else:
    k=str(int(k)+1)
    l=[]
    m=""
    for i in k:
    l.append(i)
    mid=int(len(k)/2)
    i=mid-1
    if (len(k)%2)==0:
    j=mid
    while (l[i]==l[j]):
    i-=1
    j+=1
    if (l[i]=0:
    l[mid-1]=str(int(l[mid-1])+1)
    for k in range(0,mid):
    m=m+l[k]
    m=m+m[::-1]
    else:
    j=mid+1
    lhs=False
    while (l[i]==l[j]):
    i-=1
    j+=1
    if (l[i]=0:
    if int(l[mid])==9:
    l[mid-1]=str(int(l[mid-1])+1)
    lhs=True
    else:
    l[mid]=str(int(l[mid])+1)
    for k in range(0,mid):
    m=m+l[k]
    if lhs:
    m=m+'0'+m[::-1]
    else:
    m=m+l[mid]+m[::-1]
    print(m)


    used the explanation mentioned above still getting a tle

    ReplyDelete
  8. Unknown3 September 2020 at 07:00

    so macros boring

    ReplyDelete
  9. Unknown23 September 2020 at 01:49

    very very useful ,thanks for the excellent explaination

    ReplyDelete
  10. Unknown28 November 2020 at 00:07

    #include
    #include
    #define ll long long
    using namespace std;

    ll reverse(ll num)
    {
    ll sum=0,rev;
    while (num!=0)
    {
    rev = num%10;
    sum = (sum*10) + rev;
    num=num/10;
    }
    return sum;
    }

    ll numcount(ll num)
    {
    ll count=0;
    while (num!=0)
    {
    num = num/10;
    count++;
    }
    return count;
    }

    int main()
    {
    int T;
    ll half,num,half_num,digits,rev_digits,mul_half_num;
    ll add_half_num;
    cin >> T;
    while (T--)
    {
    cin >> num;
    digits = numcount(num);
    half = digits / 2;
    if(num == 0012100) {cout << 0013100 <= 0 && num <= 8)
    {
    cout << num + 1 << endl;
    }
    else if(num == 9) {cout << num+2 <=10){ // even
    ll power = pow(10,half);
    if(half == 2) {power = 100;}
    else if(half == 4) {power = 10000;}
    else if(half == 6) {power = 1000000;}
    else if(half == 8) {power = 100000000;}
    half_num = num / power;
    rev_digits = reverse(half_num);
    mul_half_num = half_num * power;
    add_half_num = mul_half_num + rev_digits;
    if(add_half_num <= num)
    {
    half_num = num / power;
    half_num +=1;
    rev_digits = reverse(half_num);
    mul_half_num = half_num * power;
    add_half_num = mul_half_num +rev_digits ;
    cout << add_half_num <= 10){ // odd
    ll omit_one_dig;
    ll power = pow(10,half);
    if (half == 2){power = 100;}
    else if (half == 4){power = 10000;}
    else if (half == 6){power = 1000000;}
    else if (half == 8){power = 100000000;}
    half_num = num / power;
    omit_one_dig = half_num /10;
    rev_digits = reverse(omit_one_dig);
    mul_half_num = half_num * power;
    add_half_num = mul_half_num + rev_digits;
    if(add_half_num <= num)
    {
    half_num = num / power;
    half_num += 1;
    omit_one_dig = half_num / 10;
    rev_digits = reverse(omit_one_dig);
    mul_half_num = half_num * power;
    add_half_num = mul_half_num + rev_digits;
    cout << add_half_num <<endl;
    }
    else{
    cout << add_half_num << endl;
    }
    }
    else{
    cout << 00 <<endl;
    }
    }

    return 0;
    }



    What's wrong with this code

    ReplyDelete
  11. Anonymous29 September 2024 at 13:25

    I'd been stuck on this for ages getting wrong answers but all the test data I tried worked until I found this blog. I tried your two numbers and I finally could find and fix the bug in my program - thank you!

    ReplyDelete

Subscribe to: Post Comments (Atom)