263 - Number Chains

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

#263 .. plz help :~~~

Post by Frostina » Tue Feb 03, 2004 5:07 am

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]
Thanks for your help ! ;)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Feb 03, 2004 9:40 am

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

Post by waqar qayyum » Wed Jul 28, 2004 12:00 pm

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
Location: Dhaka, Bangladesh

Post by Junayeed » Mon Sep 13, 2004 3:56 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
Location: Dhaka, Bangladesh

Post by Junayeed » Mon Sep 13, 2004 2:55 pm

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

263 Gives output limite exit.please help

Post by efr_shovo » Wed Sep 29, 2004 9:52 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

Post by efr_shovo » Thu Dec 02, 2004 9:28 am

Here Is My Code.Please Help Me.
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

Post by camus » Tue May 17, 2005 8:57 pm

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

Post by thinker_bd » Sun Jun 12, 2005 8:01 pm

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;
}

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Sun Jun 12, 2005 11:35 pm

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

Post by thinker_bd » Mon Jun 13, 2005 4:35 am

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.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Jun 13, 2005 11:25 am

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

Post by thinker_bd » Tue Jun 14, 2005 8:58 pm

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.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Tue Jun 14, 2005 9:44 pm

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

Post by thinker_bd » Wed Jun 15, 2005 8:07 pm

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

Post Reply

Return to “Volume 2 (200-299)”