## 263 - Number Chains

Moderator: Board moderators

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am

### #263 .. plz help :~~~

Why it's output limit exceed :~~~

if n=0, it'll break..><

help me, plz...

[c]#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int rev(int n) {
int m;
for (m=0;n;n/=10) {
m*=10;
m+=n%10;
}
return m;
}
int sort(int n) {
int d[10], i, m;
for (i=0;n;i++) {
d = n%10;
n/=10;
}
qsort(d,i,sizeof(int),comp);
for (i--,m=0;i>=0;i--) {
m*=10;
m+=d;
}
return m;
}
int main(void) {
int n, m, ans, pre, cnt;
while(scanf("%d",&n)==1) {
if (!n) break;
printf("Original number was %d\n",n);
for (pre=-1,cnt=1;;cnt++) {
n = sort(n);
m = rev(n);
ans = n-m;
printf("%d - %d = %d\n", n, m, ans);
if (pre==ans) break;
pre = ans;
n = ans;
}
printf("Chain length %d\n\n",cnt);
}
return 0;
} [/c]

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Try the test case 59994.

waqar qayyum
New poster
Posts: 2
Joined: Wed Jun 16, 2004 9:25 am

### i guess this is the problem

Hello

after see ur program i think u have to check the count either it is exceeding the limit from 1000 or not

may be it helps u

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
What will be the output for the above input(59994).
I am getting the output exceeded limit also.

Thanks
Junayeed

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
I got AC now. The Chain Length of 59994 is 3.

Thanks
Junayeed

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

#include<stdio.h>
#define MAX 10

long nu,a[MAX];

int separet(long n)
{
long div,mod,i=0;
div=n;
while(div!=0)
{
a=div%10;
div=div/10;
i++;
}
return i;
}

int dsort(int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[j]>a)
{
temp=a;
a=a[j];
a[j]=temp;
}
}
return 0;
}

int asort(int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[j]<a)
{
temp=a;
a=a[j];
a[j]=temp;
}
}
return 0;
}

long combain(int j)
{
long dec=0;
int i;
for(i=0;i<j;)
{
dec=(a+dec);
i++;
if(i<j)
dec*=10;

}
return dec;
}

int main()
{
int i=1,len;
long nu1=0,nu2=0,num1,num2;
while(1==scanf("%ld",&nu))
{
if(nu>=1000000000||nu<=0)
break;
printf("Original number was %ld\n",nu);
nu1=nu;
while(1)
{

if(i>1000)
break;
len=separet(nu1);
dsort(len);
num1=combain(len);
asort(len);
num2=combain(len);
nu1=num1-num2;
printf("%ld - %ld = %ld\n",num1,num2,nu1);
i++;
if(nu1==nu2)
break;
nu2=nu1;
}
printf("Chain length %d\n\n",i-1);
i=1;
}
return 0;
}

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 263 - Number Chains

It gives Runtime Error (SIGSEGV)

#include<stdio.h>
#define MAX 10

long nu,a[MAX],stor[1001];

int separet(long n)
{
long div,mod,i=0;
div=n;
while(div!=0)
{
a=div%10;
div=div/10;
i++;
}
return i;
}

int dsort(int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[j]>a)
{
temp=a;
a=a[j];
a[j]=temp;
}
}
return 0;
}

int asort(int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[j]<a)
{
temp=a;
a=a[j];
a[j]=temp;
}
}
return 0;
}

long combain(int j)
{
long dec=0;
int i;
for(i=0;i<j;)
{
dec=(a+dec);
i++;
if(i<j)
dec*=10;

}
return dec;
}

void main()
{
int i=1,len,k=0,mu=0,l;
long nu1=0,num1,num2;
while(1==scanf("%ld",&nu))
{
if(nu>=1000000000||nu<=0)
break;
printf("Original number was %ld\n",nu);
nu1=nu;
while(1)
{

if(i>1000)
break;
len=separet(nu1);
dsort(len);
num1=combain(len);
asort(len);
num2=combain(len);
stor[k++]=nu1=num1-num2;
printf("%ld - %ld = %ld\n",num1,num2,nu1);
i++;
for(l=0;l<k-1;l++)
{
if(stor[l]==nu1)
{
mu=1;
break;
}
}

if(mu==1)
break;
}
printf("Chain length %d\n\n",i-1);
i=1;
mu=0;
for(l=0;l<k;l++)
stor[l]=-1;
}
}

camus
New poster
Posts: 4
Joined: Sat Jan 22, 2005 8:30 am
why not 2??

59994
99954 - 45999 = 53955
99953 - 35999 = 59994 <- original one...

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

### why WA in 263. is there any special caseplz help me

i dont understand why i got WA in this problem is there any special case.
my code is given bellow. please say what is my wrong.

Code: Select all

``````#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int num[10];

int cmp(const void *a,const void *b)

{
int *p=(int*)a;
int *q=(int*)b;

if(*p>*q)
return 1;

else if(*p<*q)
return -1;

else
return 0;
}

int digit_counter(int intiger)
{
int n=intiger,count=0;
while(1)
{
if(n==0)
break;
else
n=n/10;
count++;
}
return count;
}

void intiger2array(int intiger,int count)
{
int i;
int a=intiger,power=count;
for(i=0;i<count;i++)
{
num[i]=a%10;
a=a/10;
}
}

int array2intiger(int array[10],int count)
{
int i,p=count,intiger=0;

for(i=0;i<count;i++)
{
p=p-1;
intiger+=(num[i]*((int)(pow(10,p))));
}
return intiger;
}

int reverse_integer( int b,int count)
{
int i,rev=0,k2=0,p=count,a=b;

for(i=0;i<count;i++)
{
k2=a%10;
a=a/10;
p=p-1;
rev+=(k2*((int)(pow(10,p))));

}
return rev;
}

int conv_asnd(int intiger,int count)
{
int asnd;

intiger2array(intiger,count);
qsort(num,count,sizeof(num[0]),cmp);
asnd=array2intiger(num,count);

return asnd;
}

int main()
{
int i,test=5000;
int intiger,asnd,dsnd,c1,c2;
//	freopen("263.txt","r",stdin);
while(test--)
{
scanf("%d",&intiger);
if(intiger==0)
break;
int prev_results[10000];
int loop=0,jk=0;
printf("Original number was %d\n",intiger);
int j=0;
while(1)
{
loop++;

c1=digit_counter(intiger);
asnd=conv_asnd(intiger,c1);

c2=digit_counter(intiger);
dsnd=reverse_integer(asnd,c2);
int temp;
int result=dsnd-asnd;
printf("%d - %d = %d\n",dsnd,asnd,result);
for(i=0;i<=j;i++)
{
if(prev_results[i]==result)
{
temp=prev_results[i];
break;
}
}
if(temp==result)
break;
prev_results[j++]=result;

intiger=result;
}
printf("Chain length %d\n\n",loop);

}

return 0;
}
``````

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
I think the following input will break your program.

Code: Select all

``````123456789
123456789
0
``````
You should never take more than you give in the circle of life.

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

### for the test case my program is right but WA

for the input 123456789. it is in the sample input i test it. following output occur.

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

please check my prog throwly and say what is my wrong so that i got wrong answer.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
What I told you is to test the program for repeating inputs. I have a feeling that your previous_result array is not cleared after the first test case. So, if the same input is given consecutively, your program shoud fail. However, does your code work when 123456789 is given twice as shown in my input set?
You should never take more than you give in the circle of life.

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

### i modified it but still wrong answer

i modified it but still WA
see my modified code

Code: Select all

``````#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int num[10];

int cmp(const void *a,const void *b)

{
int *p=(int*)a;
int *q=(int*)b;

if(*p>*q)
return 1;

else if(*p<*q)
return -1;

else
return 0;
}

int digit_counter(int intiger)
{
int n=intiger,count=0;
while(1)
{
if(n==0)
break;
else
n=n/10;
count++;
}
return count;
}

void intiger2array(int intiger,int count)
{
int i;
int a=intiger,power=count;
for(i=0;i<count;i++)
{
num[i]=a%10;
a=a/10;
}
}

int array2intiger(int array[10],int count)
{
int i,p=count,intiger=0;

for(i=0;i<count;i++)
{
p=p-1;
intiger+=(num[i]*((int)(pow(10,p))));
}
return intiger;
}

int reverse_integer( int b,int count)
{
int i,rev=0,k2=0,p=count,a=b;

for(i=0;i<count;i++)
{
k2=a%10;
a=a/10;
p=p-1;
rev+=(k2*((int)(pow(10,p))));

}
return rev;
}

int conv_asnd(int intiger,int count)
{
int asnd;

intiger2array(intiger,count);
qsort(num,count,sizeof(num[0]),cmp);
asnd=array2intiger(num,count);

return asnd;
}

int main()
{
int prev_results[10000];
int i,test=5000;
int intiger,asnd,dsnd,c1,c2;
//freopen("263.txt","r",stdin);
while(test--)
{

scanf("%d",&intiger);
if(intiger==0)
break;

int loop=0,jk=0;
printf("Original number was %d\n",intiger);
int j=0;
memset(prev_results,0,sizeof(prev_results));
while(1)
{
loop++;

c1=digit_counter(intiger);
asnd=conv_asnd(intiger,c1);

c2=digit_counter(intiger);
dsnd=reverse_integer(asnd,c2);
int temp=-1;
int result=dsnd-asnd;
printf("%d - %d = %d\n",dsnd,asnd,result);
for(i=0;i<=j;i++)
{
if(prev_results[i]==result)
{
temp=prev_results[i];
break;
}
}
if(temp==result)
break;
else
prev_results[j++]=result;

intiger=result;
}
printf("Chain length %d\n\n",loop);

}

return 0;
}

``````
in my code i just modified temp=-1 and memset the array prev_results.
now see my output for the following input.

input:

Code: Select all

``````123456789
123456789
123456789
123456789
0
``````
output:

Code: Select all

``````Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Press any key to continue
``````
i think all of these are ok but why still i got WA . PLEASE HELP ME.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Check the sample I/O carefully. Does your program exactly match the sample output for this case?

Code: Select all

``````444
``````
You should never take more than you give in the circle of life.

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

### thanx i got accepted

thanx Mr. Rahman i got accpeted . just memeset my array with -1 and got accpted