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

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

263 - TLE in Java

Post by wjomlex » Sat Dec 27, 2008 11:52 am

I'm getting TLE, but I've tried to optimize my code as much as is reasonable. The only meaningful improvement I can see is that when I search for previous numbers in the chain I could use a binary search, but then I'd have to sort the array, and that would take even longer than doing a linear search. Is this just yet another one of those problems that can't be done in time in Java? I don't see anybody that's managed this in Java on the forums.

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String args[]) throws IOException
	{
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));

		while(true)
		{
			int n = Integer.parseInt(scan.readLine());

			if(n == 0)
				break;

			int[] p = new int[1005];
			int pn = 1;
			p[0] = n;

			System.out.println("Original number was " + n);

			while(true)
			{
				String str = n + "";

				int[] tmp = new int[str.length()];

				for(int i=0;i < tmp.length;i++)
					tmp[i] = str.charAt(i) - '0';

				Arrays.sort(tmp);

				int ia = 0;
				int ib = 0;

				for(int i=0;i < tmp.length;i++)
				{
					ia = (ia*10) + tmp[i];
					ib = ib + tmp[i] * (int)Math.pow(10,i);
				}

				n = ib - ia;
				System.out.println(ib + " - " + ia + " = " + n);

				boolean found = false;
				for(int i=0;i < pn;i++)
					if(p[i] == n)
						found = true;

				if(!found)
					p[pn++] = n;
				else
				{
					System.out.println("Chain length " + pn);
					System.out.println();
					break;
				}
			}
		}
	}
}

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

Re: 263 - TLE in Java

Post by annhy » Thu Mar 19, 2009 4:33 pm

You can try StringBuilder as a buffer rather than using a lot of System.out.println().
Then call the System.out.print() only once before your program exit.

It can highly improves your Java I/O.
Good luck! :D

cse08_konok
New poster
Posts: 1
Joined: Sat Nov 07, 2009 12:05 pm

263

Post by cse08_konok » Sun Dec 13, 2009 1:36 pm

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50000

int compare (const void * a, const void * b)
{
  return ( *(char*)b - *(char*)a );
}
int mysearch(long long i,long long *judge, long long j)
{
long low=1,mid,high;
high=j-1;
mid=(low+high)/2;
while(low<=high){
	if(i<judge[mid])high=mid-1;
	else if(i>judge[mid])low=mid+1;
	else return 1;
	mid=(low+high)/2;
}
return 0;
}
 
 
 
int main ()
{
long long i,j,k,x,prnt=0;
int xa,ya,za;
char tempa;
char number[30000];
long long judge[50000];
while(gets(number)){
	if(!number[0])break;
	printf("Original number was %s\n",number);
	 for(j=1;j<=MAX;j++){
		x=strlen(number);
		qsort(number,x,sizeof(char),compare);
		sscanf(number,"%lld",&i);
		za=strlen(number);
		xa=za-1;
		for(ya=0,xa;ya<(za/2);ya++,xa--){
			tempa=number[ya];
			number[ya]=number[xa];
			number[xa]=tempa;
		}
		sscanf(number,"%lld",&k);
		printf("%lld - %lld = ",i,k);
		i-=k;
		sprintf(number,"%lld",i);
		printf("%lld\n",i);
                 if(mysearch(i,judge,j))break;
		xa=(int)j;
		while((xa>1)&&(judge[xa-1]>i)){
			judge[xa]=judge[xa-1];
			xa--;
		}
		judge[xa]=i;
	}
	printf("Chain length %lld\n\n",j);
}
return 0;
}

every time i'm getting wrong answer. plz anyone help......

jfvs
New poster
Posts: 12
Joined: Wed Feb 02, 2011 10:40 am

WA in 263... help please

Post by jfvs » Thu Mar 31, 2011 8:50 pm

Im getting WA in this C++ code, I got the java version of this accepted... so I dont know whats happening here...

Code: Select all

#include <cstdio>
#include <algorithm>
#include <map>
#include <string.h>
#include <cstdlib>

using namespace std;
void ltos(long n, char *c){
	long copy = n;
	int size = strlen(c), i = size - 1, nsize = 0;
	for(; copy != 0; i--){
		c[i] = (copy % 10) + '0';
		copy /= 10;
		nsize++;
	}
	i = 0;
	for(int j = size - nsize; j < size; i++, j++) c[i] = c[j];
	c[i] = '\0';
}

int main(){
	char numb[11], cnumb[11];
	map<char*, char*> resps;
	while(scanf("%s", &numb) != EOF && strcmp(numb, "0") != 0){
		strcpy(cnumb, numb);
		if(resps.find(numb) == resps.end()){
			char resp[10000];
			sprintf(resp, "Original number was %s\n", numb);
			bool go = true;
			map<long, int> mp;
			mp[atol(numb)] = 1;
			int cycle = 0;
			while(go){
				int size = strlen(numb);
				sort(numb, numb + size);
				long desc = atol(numb);
				char ascc[size];
				for(int i = size -1, j = 0; i >= 0; i--, j++) ascc[j] = numb[i];
				long asc = atol(ascc), rest = asc - desc;
				sprintf(resp, "%s%ld - %ld = %ld\n", resp, asc, desc, rest);
				if(mp.find(rest) == mp.end()){
					mp[rest] = 1;
				}else{
					go = false;
				}
				ltos(rest, numb);
				cycle++;
			}
			sprintf(resp, "%sChain length %d\n\n", resp, cycle);
			resps[cnumb] = resp;
		}
		printf(resps[cnumb]);
	}
	return 0;
}
thanks

coralblue
New poster
Posts: 1
Joined: Sun Jan 27, 2013 11:18 am

Re: 263 - TLE in Java

Post by coralblue » Sun Jan 27, 2013 11:22 am

@annhy thanks for the tip!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 263 - RE

Post by shuvokr » Fri Mar 22, 2013 9:33 pm

Why i got RE , please anyone help

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

#define sf scanf
#define pf printf

void convert(int num);
int cou;

int main()
{
    char inum[11];
    int i, j, tmp, sk, len, bs, sb, carry, t, k, num, c, cc;
    memset(inum, 0, 11);
    while(gets(inum))
    {
        if(inum[0] == '0') return 0;
        sscanf(inum, "%d", &num);
        len = strlen(inum);
        cc = len / 2;
        c = len - 1;

        bool ck = true;
        for(i = 0; i < cc; i++)
        {
            if(inum[i] != inum[c--])
                ck = false;
        }

        if(ck)
        {
            pf("Original number was %d\n", num);
            pf("%d - %d = 0\n", num, num);
            puts("0 - 0 = 0");
            puts("Chain length 2");
        }
        else
        {
            sort(inum, inum + len);
            for(i = 0; i < len; i++)
                if(inum[i] != '0') break;
            sb = 0;
            carry = 0;
            k = (len - i) - 1;
            for(j = i; j < len; j++)
            {
                tmp = (inum[j] - 48);
                t = pow(10, k);
                if(t % 10 != 0 && t != 1) t++;
                k--;
                sb += tmp * t;
            }
            bs = 0;
            k = len - 1;
            if(inum[len - 1] == '0') bs = 0;
            else
            {
                for(i = len - 1; i >= 0; i--)
                {
                    tmp = (inum[i] - 48);
                    t = pow(10, k);
                    if(t % 10 != 0 && t != 1) t++;
                    k--;
                    bs += tmp * t;
                }
            }
            k = bs - sb;
            cou = 1;
            pf("Original number was %d\n%d - %d = %d\n", num, bs, sb, k);
            if(k == num)
            {
                puts("Chain length 1");
            }
            else
            {
                convert(k);
            }
        }
        puts("");
    }
}
void convert(int num)
{
    int i, j, k = num, tmp, len = log10(k) + 1, sb, bs, t;
    char ch[11];
    memset(ch, 0, 11);
    t = 0;
    for(i = 0; i < len; i++)
    {
        tmp = k % 10;
        ch[t++] = tmp + 48;
        k /= 10;
    }
    sort(ch, ch + len);
    for(i = 0; i < len; i++)
        if(ch[i] != '0') break;
    sb = 0;
    k = (len - i) - 1;
    for(j = i; j < len; j++)
    {
        tmp = (ch[j] - 48);
        t = pow(10, k);
        if(t % 10 != 0 && t != 1) t++;
        k--;
        sb += (tmp * t);
    }
    bs = 0;
    k = len - 1;
    if(ch[len - 1] == '0') bs = 0;
    else
    {
        for(i = len - 1; i >= 0; i--)
        {
            tmp = (ch[i] - 48);
            t = pow(10, k);
            if(t % 10 != 0 && t != 1) t++;
            k--;
            bs += (tmp * t);
        }
    }
    k = bs - sb;
    cou++;
    pf("%d - %d = %d\n", bs, sb, k);
    if(k == num)
    {
        pf("Chain length %d\n", cou);
        return;
    }
    else
    {
        convert(k);
    }
}

Code: Select all

enjoying life ..... 

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 263 - TLE in Java

Post by shuvokr » Fri Mar 22, 2013 10:02 pm

Try rewriting your code without using floating point.

Code: Select all

enjoying life ..... 

rukhsana
New poster
Posts: 1
Joined: Mon Jan 20, 2014 12:34 pm

Re: 263 - TLE in Java

Post by rukhsana » Mon Jan 20, 2014 12:45 pm

I think there is something wrong with the judge for this problem then. I submitted a program that checked for palindromes of lengths 3 and 4 only, and it got Accepted. However, it does not pass your input :\
Get up to date braindumps questions to practice for Stanford University exam and complete your certification on time.if you need more information see main website Facebook or see California University of Pennsylvania page.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 263 - TLE in Java

Post by uDebug » Fri May 30, 2014 1:23 pm

Here's some input / output I found useful during testing / debugging.

Remember to print a newline after every test case - including the last one.

Input:

Code: Select all

92482438
57878377
34131232
3434453
9833
1
3589458
0
AC Output:

Code: Select all

Original number was 92482438
98844322 - 22344889 = 76499433
99764433 - 33446799 = 66317634
76664331 - 13346667 = 63317664
76664331 - 13346667 = 63317664
Chain length 4

Original number was 57878377
88777753 - 35777788 = 52999965
99996552 - 25569999 = 74426553
76554432 - 23445567 = 53108865
88655310 - 1355688 = 87299622
99876222 - 22267899 = 77608323
87763320 - 2336778 = 85426542
86554422 - 22445568 = 64108854
88654410 - 1445688 = 87208722
88772220 - 2227788 = 86544432
86544432 - 23444568 = 63099864
99866430 - 3466899 = 96399531
99965331 - 13356999 = 86608332
88663320 - 2336688 = 86326632
86663322 - 22336668 = 64326654
66654432 - 23445666 = 43208766
87664320 - 2346678 = 85317642
87654321 - 12345678 = 75308643
87654330 - 3345678 = 84308652
88654320 - 2345688 = 86308632
88663320 - 2336688 = 86326632
Chain length 20

Original number was 34131232
43332211 - 11223334 = 32108877
88773210 - 1237788 = 87535422
87554322 - 22345578 = 65208744
87654420 - 2445678 = 85208742
88754220 - 2245788 = 86508432
88654320 - 2345688 = 86308632
88663320 - 2336688 = 86326632
86663322 - 22336668 = 64326654
66654432 - 23445666 = 43208766
87664320 - 2346678 = 85317642
87654321 - 12345678 = 75308643
87654330 - 3345678 = 84308652
88654320 - 2345688 = 86308632
Chain length 13

Original number was 3434453
5444333 - 3334445 = 2109888
9888210 - 128889 = 9759321
9975321 - 1235799 = 8739522
9875322 - 2235789 = 7639533
9765333 - 3335679 = 6429654
9665442 - 2445669 = 7219773
9777321 - 1237779 = 8539542
9855432 - 2345589 = 7509843
9875430 - 345789 = 9529641
9965421 - 1245699 = 8719722
9877221 - 1227789 = 8649432
9864432 - 2344689 = 7519743
9775431 - 1345779 = 8429652
9865422 - 2245689 = 7619733
9776331 - 1336779 = 8439552
9855432 - 2345589 = 7509843
Chain length 16

Original number was 9833
9833 - 3389 = 6444
6444 - 4446 = 1998
9981 - 1899 = 8082
8820 - 288 = 8532
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 6

Original number was 1
1 - 1 = 0
0 - 0 = 0
Chain length 2

Original number was 3589458
9885543 - 3455889 = 6429654
9665442 - 2445669 = 7219773
9777321 - 1237779 = 8539542
9855432 - 2345589 = 7509843
9875430 - 345789 = 9529641
9965421 - 1245699 = 8719722
9877221 - 1227789 = 8649432
9864432 - 2344689 = 7519743
9775431 - 1345779 = 8429652
9865422 - 2245689 = 7619733
9776331 - 1336779 = 8439552
9855432 - 2345589 = 7509843
Chain length 12

Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Shafayat
New poster
Posts: 7
Joined: Mon Jan 19, 2015 11:32 am

Why WA in 263 - Number Chains?

Post by Shafayat » Mon Jan 19, 2015 11:39 am

Code: Select all

#include <stdio.h>
#include<string.h>
#include<math.h>

int main ()
{
    long long int a,b,c,d,e,f[10],g,h,i,j=0,k[2000],l,n,o=0,p;
    char m[100];
    while(scanf("%s",m))
    {
        if(strcmp(m,"0")==0)
            break;
        a=0;
        n=0;
        if(o>0)
            printf("\n");
        p=0;
        while(a!=1)
        {
            for(c=0;c<10;c++)
                f[c]=0;
            d=0;
            e=1;
            b=strlen(m);
            for(c=b-1;c>=0;c--)
            {
                d=d+(m[c]-'0')*e;
                e=e*10;
                f[m[c]-'0']++;
            }
            if(p==0)
                printf("Original number was %lld\n",d);
            p++;
            if(n==0)
            	k[n]=d;
            g=0;
            e=1;
            i=0;
            j=1;
            for(c=0;c<10;c++)
            {
                if(f[c]>0)
                {
                    for(h=1;h<=f[c];h++)
                    {
                        g=g+c*e;
                        e=e*10;
                    }
                }
                if(f[9-c]>0)
                {
                    for(h=1;h<=f[9-c];h++)
                    {
                        i=i+(9-c)*j;
                        j=j*10;
                    }
                }
            }
            l=g-i;
            printf("%lld - %lld = %lld\n",g,i,l);
            for(c=0;c<=n;c++)
            {
                if(l==k[c])
                {
                    break;
                }
            }
            if(c<n+1)
            {
                a=1;
                printf("Chain length %lld\n",n+1);
                break;
            }
            n++;
            k[n]=l;
            d=log10(l);
            if(l<10)
                d=0;
            for(c=d;c>=0;c--)
            {
                m[c]=l%10+'0';
                l=l/10;
            }
            m[d+1]='\0';
        }
        p=0;
        o++;
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 263 - Number Chains

Post by brianfry713 » Mon Jan 19, 2015 9:44 pm

After each number chain and chain length, including the last one, there should be a blank line.
Check input and AC output for thousands of problems on uDebug!

Shafayat
New poster
Posts: 7
Joined: Mon Jan 19, 2015 11:32 am

Re: 263 - Number Chains

Post by Shafayat » Tue Jan 20, 2015 7:36 pm

Thanks a lot. Got accepted

sabuj_aiub14
New poster
Posts: 2
Joined: Thu Jul 02, 2015 2:56 pm

Re: 263 - Number Chains

Post by sabuj_aiub14 » Thu Jul 02, 2015 3:07 pm

why wa???
please help...
here is my code...

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[100],b[100];
int c[10000];
int cmpfunc2(const void *a,const void *b)
{
    return (*(int*)a-*(int *)b);
}
int cmpfunc(const void *a,const void *b)
{
    return (*(int*)b-*(int *)a);
}

int main()
{
    char str[100],str1[1000];

    int size1,i,s1,s2,s,flag,t,m,mod,n1,q,count1;
    while(scanf("%s",str)==1)
    {
        t=0;
        flag=0;
        count1=0;
        if(str[0]=='0')
            break;
        cout<<"Original number was "<<str<<endl;
    while(flag==0)
    {
        size1=strlen(str);
        for(i=0;i<size1;i++)
        {
            a[i]=str[i]-'0';
            b[i]=str[i]-'0';
        }
        qsort(a,size1,sizeof(int),cmpfunc);
        qsort(b,size1,sizeof(int),cmpfunc2);
        s1=0;
        s2=0;
        for(int j=0;j<size1;j++)
        {
            s1=s1*10+a[j];
            s2=s2*10+b[j];
        }
        s=s1-s2;

        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
        //cout<<s;
        c[t]=s;
        n1=0;
        q=s;
        while(s>0)
        {
            mod=s%10;
            s=s/10;

            str[n1]=mod+'0';
            n1++;

        }


        if(q==0)
        {
            flag=1;
            count1=count1+2;

             flag=1;
             s1=s2=s=0;
             break;


        }
        else
        {
            if(t>0)
            {
                m=t-1;
                while(m>=0)
                {
                    if(c[t]==c[m])
                    {

                        flag=1;
                        break;
                    }
                    m--;
                }
            }
        }
        count1++;
        t++;

    }
    if(q==0)
    {
        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
    }
    cout<<"Chain length "<<count1<<endl<<endl;

    }


return 0;
}

BaronRED
New poster
Posts: 3
Joined: Sun Jun 28, 2015 4:40 pm

Re: 263 - Number Chains

Post by BaronRED » Thu Jul 02, 2015 4:32 pm

Put your source code inside the "code" tags to keep the indentation, w/o it it's very difficult to read the code!

sabuj_aiub14
New poster
Posts: 2
Joined: Thu Jul 02, 2015 2:56 pm

Re: 263 - Number Chains

Post by sabuj_aiub14 » Thu Jul 02, 2015 5:11 pm

why wa pls help....

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[100],b[100];
long long c[10000];
int cmpfunc2(const void *a,const void *b)
{
    return (*(int*)a-*(int *)b);
}
int cmpfunc(const void *a,const void *b)
{
    return (*(int*)b-*(int *)a);
}

int main()
{
    char str[100],str1[1000];

    int size1,i,s1,s2,s,flag,t,m,mod,n1,q,count1;
    while(scanf("%s",str)==1)
    {
        t=0;
        flag=0;
        count1=0;
        if(str[0]=='0')
            break;
        cout<<"Original number was "<<str<<endl;
    while(flag==0)
    {
        size1=strlen(str);
        for(i=0;i<size1;i++)
        {
            a[i]=str[i]-'0';
            b[i]=str[i]-'0';
        }
        qsort(a,size1,sizeof(int),cmpfunc);
        qsort(b,size1,sizeof(int),cmpfunc2);
        s1=0;
        s2=0;
        for(int j=0;j<size1;j++)
        {
            s1=s1*10+a[j];
            s2=s2*10+b[j];
        }
        s=s1-s2;

        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
        //cout<<s;
        c[t]=s;
        n1=0;
        q=s;
        while(s>0)
        {
            mod=s%10;
            s=s/10;

            str[n1]=mod+'0';
            n1++;

        }


        if(q==0)
        {
            flag=1;
            count1=count1+2;

             flag=1;
             s1=s2=s=0;
             break;


        }
        else
        {
            if(t>0)
            {
                m=t-1;
                while(m>=0)
                {
                    if(c[t]==c[m])
                    {

                        flag=1;
                        break;
                    }
                    m--;
                }
            }
        }
        count1++;
        t++;

    }
    if(q==0)
    {
        cout<<s1<<" - "<<s2<<" = "<<s<<endl;
    }
    cout<<"Chain length "<<count1<<endl<<endl;

    }


return 0;
}

Post Reply

Return to “Volume 2 (200-299)”