## 263 - Number Chains

Moderator: Board moderators

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
The given number is not consiedered as a member of the chain.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

### 263 WA plz help

here is my code plz help me
#include<stdio.h>
#include<string.h>
void sort(char* a,int l)
{
int i,j,temp;
for(i=0;i<l-1;i++)
{
for(j=i+1;j<l;j++)
{
if(a>a[j])
{
temp=a[j];
a[j]=a;
a=temp;
}
}
}

}
void reverse(char *a,char *b,int l)
{ int i;
for(i=l-1;i>=0;i--)
b[(l-1)-i]=a;
}
void subtract(char* a,char* b,char* c,int* l)
{ int k=0,i,j,v,p,flag=1,u=0;
int o;
o=*l;
for(i=0;i<o;i++)
p=a;
for(i=0;i<(*l);i++)
{
if(a>=b)
{
c=a-b[i];
if(c[i]==0 && i==(*l)-1)
(*l)--;
if((*l)==0)
(*l)++;
flag=0;
}
if(a[i]<b[i] && a[i]!=0)
{

a[i]+=10;
a[i+1]-=1;
c[i]=a[i]-b[i];

}
if(a[i]==0 && flag==1)
{
for(j=i;;j++)
{
if(a[j]==0)
k++;
else
break;
}
a[i]=a[i]+10;
for(j=i+1;j<k;j++)
a[j]=9;
a[j]=a[j]-1;
c[i]=a[i]-b[i];
if(k==o-1)
(*l)--;
}
flag=1;
}
for(i=0;i<(*l);i++)
{
if(c[i]==0)
u++;
}
if(u==(*l))
(*l)=1;
for(i=0;i<o;i++)
printf("%d",p[(o-1)-i]);
printf(" - ");
for(i=0;i<o;i++)
if(b[(o-1)-i]!=0)
printf("%d",b[(o-1)-i]);
if((*l)==1 && b==0)
printf("%d",b);
printf(" = ");
for(i=0;i<(*l);i++)
printf("%d",c[((*l)-1)-i]);
printf("\n");
}
int compare(char* e,char* c,int l,int j)
{
int i,flag=1;
//printf("\n value of e in compare fun in % d call\n",j);
// for(i=0;i<l;i++)
//printf("%d",e[i]);
//printf("\n");
for(i=0;i<l;i++)
{
if(e[i]==c[(l-1)-i])
{
//printf("e[%d]=%d c[%d]=%d ",i,e[i],l-1-i,c[l-1-i]);
flag=0;
}
else
{
flag=1;
//printf("e[%d]=%d c[%d]=%d ",i,e[i],l-1-i,c[l-1-i]);
break;
}
//printf("\n");
}
//printf("flag=%d\n",flag);
return(flag);
}
void copy(char* c,char* a,int l)
{
int i;
for(i=0;i<l;i++)
a[i]=c[(l-1)-i];
}
void copy1(char* c,char* e,int l )
{
int i,j;

for(i=0;i<l;i++)
e[i]=c[(l-1)-i];
}
main()
{
char a,b,c,e;
int t,l,count,flag=0,i,j;
while(scanf("%s",a) && a!='0')
{
printf("Original number was ");
count=0;
l=strlen(a);
for(i=0;i<l;i++)
{
a[i]=a[i]-'0';
e[i]=a[i];
printf("%d",a[i]);
}
// printf("\ne is \n");
// for(i=0;i<l;i++)
//printf("%d",e[i]);
printf("\n");
for(t=0;;t++)
{
count++;
sort(a,l);
reverse(a,b,l);
subtract(a,b,c,&l);
for(i=0;i<count;i++)
{
flag=compare(e[i],c,l,i);
//printf("\n value of flag in main %d\n",flag);
if(flag==0)
break;
}
if(flag==0)
break;
copy(c,a,l);
copy1(c,e[count],l);

}
printf("Chain length %d\n\n",count);
for(i=0;i<20;i++)
{
a[i]='\0';
b[i]='\0';
c[i]='\0';

}
for(i=0;i<2000;i++)
for(j=0;j<20;j++)
e[i][j]='\0';
}
}

chulin nagasaki
New poster
Posts: 3
Joined: Wed Apr 26, 2006 7:06 pm

### 263... CLarification. HELP ME PLS

Would that imput be valid? Which would the output be for this imput?
192
00192
55694
what does he mean with "Note that 0 is a permitted digit"?

I GOT MANY WA

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Output for above input:

Code: Select all

``````Original number was 192
921 - 129 = 792
972 - 279 = 693
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
Chain length 5
Original number was 192
921 - 129 = 792
972 - 279 = 693
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
Chain length 5
Original number was 55694
96554 - 45569 = 50985
98550 - 5589 = 92961
99621 - 12699 = 86922
98622 - 22689 = 75933
97533 - 33579 = 63954
96543 - 34569 = 61974
97641 - 14679 = 82962
98622 - 22689 = 75933
Chain length 8
``````
So you see there is no difference between 192 and 00192. Most probably such are not there.
chulin nagasaki wrote:what does he mean with "Note that 0 is a permitted digit"?
I'm not so sure what he exactly mean. Maybe telling to continue processing when you get 0 (like the 3rd input in the problem sample) or he simply meant arranging digits, say 6509, in decreasing order you get 9650 and in increasing order you get 0569 => 569.

gabox
New poster
Posts: 2
Joined: Fri May 26, 2006 3:06 am

I think you're not giving importance to a little detail:
"4. and repeat these steps unless the new number has already appeared in the chain"

You gotta verify if the number has already appeared on the chain, so, you gotta have a register of each number and search the new number. That's all you need to fix.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

### 263 - CE

here is my code . i dont know why CE......
it compiles properly on my machine..........

[
Last edited by chetan on Wed Oct 11, 2006 3:33 pm, edited 1 time in total.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
i have modified the code a bit.
i use only C - style character arrays instead of strings.
but inspite of that judge gives me CE............
it compiles and runs properly on my machine.........
Last edited by chetan on Wed Oct 11, 2006 3:34 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
You forgot to include cstdio. This should be in C++ forum, btw.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
ok fine here is the final code and the judge gives me a WA plz give some test cases atleast ...........

Code: Select all

``````CODE DELETED AFTER AC....
``````

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

### Same problem

I have the same problem -------- 1st i got CE bcoz of ignoring cstdio but after that i have got WA plz help someone...........
Here is my code

Code: Select all

``````#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

char str,a;
int len;

void str_rev(){
int i,x = 0;
for(i=0; i<100; i++) { a[i] = 0;}
for(i=len-1; i>=0; i--)
a[x++] = str[i];
}

void strc(long long n){
char su_b;
int i=0,j,x=0;
while(n >= 10){
su_b[i++] = (n%10)+48;
n = n/10;
}
su_b[i] = n+48;
for(j=0; j<len; j++) str[j] = NULL;
for(j=i; j>=0; j--)
str[x++] = su_b[j];
str[x] = 0;

}

int main()
{
long long num1,num2,arr,sub = 0,l = 0,k,i;
char nstr;
while(gets(str) != NULL){
if(!strcmp(str,"")) break;
l = 0; sub = 0; k = 0;
len = strlen(str);
if(str == '0'){
for(i=0; i<len; i++){
if(str[i] != '0')
nstr[k++] = str[i];
}
nstr[k] = 0;
len = k;
strcpy(str, nstr);
}
printf("Original number was %s\n",str);
while(1){
sort(str,str+len);
num1 = atol(str);
str_rev();
num2 = atol(a);
sub = num2-num1;
if(l>0){
if(binary_search(arr,arr+l,sub)){
printf("%lld - %lld = %lld\n",num2,num1,sub);
printf("Chain length %lld\n",l+1);
break;
}
}
arr[l++] = sub;
sort(arr,arr+l);
printf("%lld - %lld = %lld\n",num2,num1,sub);
strc(sub);
}
printf("\n");
}
return 0;
}
``````
Plz give me some tricks plz!!!!!!!!!!!

Bappi_cuet
New poster
Posts: 14
Joined: Wed Jul 11, 2007 4:26 pm
Contact:

### Why OLE

I can't figure out why output limit excessed. I try this a lot but still OLE.

Code: Select all

``````ACCEPTED
``````
Thanks for Help.
Last edited by Bappi_cuet on Tue Sep 04, 2007 5:53 pm, edited 1 time in total.

Sohel_Cuet
New poster
Posts: 4
Joined: Thu Nov 24, 2005 5:47 am
Contact:
Hi bappy i run your code on my machine and got some bugs.Some I/O do not match with my acc code.I am giving u those I/O

Input :

Code: Select all

``````1000
100
100000000
67779000
``````
Output Of My Accepted Code :

Code: Select all

``````Original number was 1000
1000 - 1 = 999
999 - 999 = 0
0 - 0 = 0
Chain length 3

Original number was 100
100 - 1 = 99
99 - 99 = 0
0 - 0 = 0
Chain length 3

Original number was 100000000
100000000 - 1 = 99999999
99999999 - 99999999 = 0
0 - 0 = 0
Chain length 3

Original number was 67779000
97776000 - 67779 = 97708221
98772210 - 1227789 = 97544421
97544421 - 12444579 = 85099842
99885420 - 2458899 = 97426521
97654221 - 12245679 = 85408542
88554420 - 2445588 = 86108832
88863210 - 1236888 = 87626322
87663222 - 22236678 = 65426544
66554442 - 24445566 = 42108876
88764210 - 1246788 = 87517422
87754221 - 12245778 = 75508443
87554430 - 3445578 = 84108852
88854210 - 1245888 = 87608322
88763220 - 2236788 = 86526432
86654322 - 22345668 = 64308654
86654430 - 3445668 = 83208762
88763220 - 2236788 = 86526432
Chain length 17

``````
Note That for the input 67779000 your code generates infinite number of output lines!!!!!!!! Fix it.Hope you will get Acc.Good Luck.. Keep dreaming.It costs nothing but makes you living

Bappi_cuet
New poster
Posts: 14
Joined: Wed Jul 11, 2007 4:26 pm
Contact:

### Thanks!

Thanks for your sample input and output. I got the error of my and fixed it and got AC I remove my code! ---------------------------------------------
IT'S TIME TO GO AHEAD !!!!
---------------------------------------------

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

who says that the chain length of 59994 is 3,,,probably is wrong.coz my AC prgram gives 2.http://uvatoolkit.com also gives 2.
and I would like to remind u.
and repeat these steps unless the new number has already appeared in the chain
so i considered every number existing in the chain.thus initial number is one of the numbers in the chain.
if ur AC code gives 3 for 59994,ensure ,so that we can say that there is no such cases.
thanx everybody.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am