Wednesday, February 9, 2011

263-Number Chains


#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int chain[1005],N;

int findPos(int item);
int reorder(int n,int& x,int& y);

int main()
{
    int n,x,y;
   // freopen("in.txt","r",stdin);
    while(scanf("%d",&n)&&n)
    {
        N=1;
        chain[0]=n;
        printf("Original number was %d\n",n);
        for(;;)
        {
            reorder(n,x,y);
            n=x-y;
            printf("%d - %d = %d\n",x,y,n);
            if(findPos(n)==-1)
                chain[N++]=n;
            else
            {
                printf("Chain length %d\n\n",N);
                break;
            }
        }
    }
}

int findPos(int item)
{
    int i;
    for(i=0;i<N;i++)
        if(chain[i]==item)
            return i;
    return -1;
}

int reorder(int n,int& x,int& y)
{
    int num[10],i=0,j;
    x=y=0;
    while(n)
        num[i++]=n%10,n=n/10;
    sort(num,num+i);

    for(j=0;j<i;j++)
        y=y*10+num[j];
    for(j=i-1;j>=0;j--)
        x=x*10+num[j];
    return 0;
}



No comments:

Post a Comment

Note: Only a member of this blog may post a comment.