974 - Kaprekar Numbers

[Jan]

Your code doesn't even pass the samples.

[mukeshtiwari]

thnkx jan .
it was really big mistake and i haven't consider the range in which there is no number . thnkx again .

[mikimiska]

Can anyone hep?????
My code

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List vrniKaprekar(int min, int max){
        List rezultat = new ArrayList();
        for(int i = min; i <= max; i++){
            if(isKaprekar(i))
                rezultat.add(new Integer(i));
        }
        return rezultat;
    }
   
    static boolean isKaprekar(int stevilo) {
            boolean odgovor = false;
            int[] stevila = {9, 45, 55, 99, 297, 703, 999, 2223, 2728, 4879, 4950, 5050, 5292, 7272, 7777, 9999, 17344, 22222, 38962};
                for(int i = 0; i < stevila.length; i++) {
                        if(stevila[i] == stevilo) odgovor = true;
                }
           
            return odgovor;
    }
          
   
    void Begin() {
        String input;
        int n = 0;
        StringTokenizer idata;
        List rezultat = new ArrayList();
         try {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          while ((input = br.readLine()) != null){
                  if(input.equals("\r") || input.equals("")) {
                          break;
                  }
                  idata = new StringTokenizer (input);
                  int m = Integer.parseInt(idata.nextToken());
                  if(n == 0){
                	  if(m >= 1 && m <= 1000) n = m;
                      
                  }else{
                          int max = Integer.parseInt (idata.nextToken());
                          if(m > 1 && max <= 40000 && m <= max){
                                  rezultat.add(vrniKaprekar(m, max));
                          }
                          else {
                                  List neki = new ArrayList();
                                  neki.add("bla");
                                  rezultat.add(neki);
                          }
                  }
                 
                 
          }
          if(rezultat.size() == n && n >= 1 && n <= 1000){
              for(int i = 0; i < rezultat.size(); i++){
                  List rez = (List)rezultat.get(i);
                  if(rez.isEmpty()){
                       System.out.println("case #" +(i+1));
                       System.out.println("no kaprekar numbers");
                       System.out.println();
                   }
                  else if(rez.get(0).equals("bla")){}
                  else{
                       System.out.println("case #" +(i+1));
                       for(int k = 0; k < rez.size(); k++){    
                         System.out.println(rez.get(k));
                       }
                       System.out.println();
                   }
              }
          }
     }
     catch (Exception e) {
       e.printStackTrace();
     }    
     }
   
   
    public static void main(String[] args) {
        Main sem = new Main();
        sem.Begin();
    }

}

Thanks.

[apurba]

is this code is enough to generate kaprekar numbers for the problem?

here is the code.............if there is any wrong with that pls know it to me..........

Code: Select all

/*****  kaprekar numbers @ 974  *****/

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

long test,inf,sup,cse;
long square,n,m,s,flag,d;

int main()
{
	
		}
	}
	return 0;
}

enjoy programming

[Jan]

First generate all the numbers and save them in an array. Then print the numbers according to the input. Hope it helps.

[hafezhafez2008]

WHY T.L.E
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;

int main()
{

int s[1000];
long long int a,b,u,sum;
long long int z;
int t;
cin>>t;
int c=1,x=0;
while(x<t)
{

cin>>a>>b;
int j=0;

for(long long i=a;i<=b;i++)
{
u=0;
sum=0;
z=i*i;
while(z!=0)
{
z/=10;u++;
}
z=i*i;

long long int y;
int r=int(sqrt(u));
y=pow(10.0,r);
long long int x=z%y;
long long w=z/y;
sum=x+w;

if(sum==i&&x>0&&w>0)
{
s[j]=i;
j++;
}

}
if(j==0)
{
cout<<"case #"<<c<<endl;
cout<<"no kaprekar numbers"<<endl;

}
else
{
cout<<"case #"<<c<<endl;
for(int i=0;i<j;i++)
{
cout<<s;
if(i!=j-1)
cout<<endl;
}

cout<<endl;
}

c++;
x++;
}
}

[fahmi]

can any1 tell me why i m getting TLE??plzzzz help

Code: Select all

#include<stdio.h>

int kaprekar(long long n)
{
	long long i,j,c,p[100],x,y,z,f;
	x=n*n;
	i=0;
	f=0;
	while(x>0)
	{
		y=x%10;
		p[i++]=y;
		z=x/10;
		c=0;
		for(j=i-1;j>=0;j--)
		{
			c=c*10+p[j];
		}
		if(c+z==n&&c!=0&&z!=0)
		{
			f=1;
			break;
		}
		x=z;
	}
	return f;
}

int main()
{
	long long t,a,b,i,j,k,s[1000];
	scanf("%lld",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%lld %lld",&a,&b);
		printf("case #%lld\n",i);
		k=0;
		for(j=a;j<=b;j++)
		{
			if(kaprekar(j)==1)
				s[k++]=j;
		}
		if(k==0)
		{
			printf("no kaprekar numbers\n\n");
			continue;
		}
		for(j=0;j<k;j++)
			printf("%lld\n",s[j]);
		if(i<t)
			printf("\n");
	}
	return 0;
}

[sapnil]

Trying with initilize.you calculate Kaprekar numbers for each input. its kill your time.
>> there are only maximum <20 Kaprekar numbers in 40000.
Thanks

[kissu parina]

solved it by pre-calculating the numbers

[plamplam]

You don't need to send a table, my brute force algorithm gets AC in 0.036 seconds

[zhra]

Here's my code , I don't know where the wrong in it !
Can anyone help me , please ?

Code: Select all

# include <iostream>
using namespace std;

int main()
{
	//freopen("input.txt" , "r" , stdin);

	int caseN , fN , sN , part1 , part2 , nSquare , temp , nuOfDigits ,
		tensToDivision , digit ;

	bool kaprekar;

	cin>> caseN;

	for(int i=1 ; i <= caseN ; i++ )
	{		
		
		cin>> fN >> sN;
		kaprekar = false;

		cout<<"case #" << i <<endl ;
		part1  = part2 = 0;

		for(int j=fN ; j <= sN ; j++)
		{
			nSquare = temp = j*j;
			tensToDivision = 1;
			nuOfDigits = 0 ;

			if(temp < 10)
				continue;

			while (temp != 0 )
			{
				temp = temp / 10 ;
				nuOfDigits++;
				//tensToDivision *= 10;
			}
					
			if(nuOfDigits % 2 == 0)
			{
				temp = nSquare;
				int n , myNumb, result =0 ;
				for(int k=0 ; k < nuOfDigits/2 ; k++ ) 
			{
					n = temp / 10 ;
					myNumb = temp - (n*10) ;
					myNumb = myNumb*tensToDivision + result ;
					result = myNumb;
					temp = n ;

					tensToDivision *= 10 ;
				}

				part1 = nSquare / tensToDivision ;
				part2 = result ;

				/*if(part1 <= 0 || part2 <= 0)
					continue;*/

				if(part1 + part2 == j)
				{
					cout<<j<<endl;
					kaprekar = true;
				}

			}

		}

		if( !kaprekar )
		{
			cout<<"no kaprekar numbers\n";
		}

		cout<<endl;
	}

	return 0;
}

[raj]

uav says its TIME LIMIT EXCEEDED..... BUT my algorithm is nice here.......CAN ANYONE PLEASE HELP ME????

import java.io.*;
import java.util.*;
class Main{
public static void main(String [] args)throws IOException{
final BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
PrintWriter z = new PrintWriter(System.out);
int T = Integer.valueOf(k.readLine());
int c = 0,x = 1,max = 0,min = 0,p=0;
while(c<T)
{
int d = 1;
String i = k.readLine();
Scanner a = new Scanner(i);
int [] h = new int [2];
int q = 0;
while(a.hasNextInt())
{
h[q] = a.nextInt();
q++;
}
if(h[0]>h[1])
{
max = h[0];
min = h[1];
p = min;
}
else
{
max = h[1];
min = h[0];
p = min;
}
System.out.println("case #"+x);
x++;
while(min<=max)
{
String s = ""+(min*min);
String g = "";
while(!(s.length()==1))
{
String y = ""+s.charAt(0);
g = g + y;
int n = Integer.valueOf(g);
s = s.substring(1);
int m = Integer.valueOf(s);
if((m+n==min) && m>0)
{
d=0;
z.println(min);
z.flush();
break;
}
}
min = ++p;
}
if(!(d==0))
{
z.println("no kaprekar numbers");
z.flush();
}
c++;
if(!(c==T))
{
z.println();
z.flush();
}
}
}
}

[brianfry713]

Precalculate all the Kaprekar Numbers.

[raj]

Precalculate all the Kaprekar Numbers.

yes sir i chequed from wikipidia all the kaprekar numbers are existed in my code.........

[raj]

online judge says its "TIME LIMIT EXCEED" i cheque all the KAPREKAR numbers from wikipidie......
all of them are correct.......PLEASE anyone kindly help me???

import java.io.*;
import java.util.*;
public class Main{
public static void main(String [] args)throws IOException{
final BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
PrintWriter z = new PrintWriter(System.out);
int T = Integer.valueOf(k.readLine());
int c = 1,max = 0,min = 0,p=0;
while(c<=T)
{
int d = 1;
StringTokenizer sb = new StringTokenizer(k.readLine());
int i1 = 0,i2 = 0;
while(sb.hasMoreTokens())
{
i1 = Integer.valueOf(sb.nextToken());
i2 = Integer.valueOf(sb.nextToken());
}
if(i1>i2)
{
max = i1;
min = i2;
p = min;
}
else
{
max = i2;
min = i1;
p = min;
}
System.out.println("case #"+c);
while(min<=max)
{
String s = ""+(min*min);
String g = "";
while(!(s.length()==1))
{
String y = ""+s.charAt(0);
g = g + y;
int n = Integer.valueOf(g);
s = s.substring(1);
int m = Integer.valueOf(s);
if((m+n==min) && m>0)
{
d=0;
z.println(min);
z.flush();
break;
}
}
min = ++p;
}
if(!(d==0))
{
z.println("no kaprekar numbers");
z.flush();
}
if(!(c==T))
{
z.println();
z.flush();
}
c++;
}
}
}