944 - Happy Numbers

[Shafaet_du]

Any permutation of the digits of a happy (unhappy) number must also be happy (unhappy). This follows from the fact that addition is commutative.

This is the most important hint for this problem,use dp and optimize your code using this principle.

[plamplam]

I disagree. I didn't even consider that line. (Although you need that line and even more if you aim to get a spot in the top 20) There is a smarter and simpler solution. I just used simple brute force to store all the happy numbers and the number of iterations required(if any) in 2 arrays. However you need to know when to stop. For this I used cycle detection. Between 1 and 99999 the maximum iterations required for a happy number is always less than 10. You can use cycle detection to find this. Using DP would probably get a higher runtime.

P.S I see you got AC in 0.888s my solution got AC in 0.128s with simple brute force

[Farsan]

Always output a blank line between test cases even if there is no happy numbers in any test case interval.

[sifatoooo]

WA again and again

Code:

Code: Select all

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader isr=new InputStreamReader(System.in);
		Scanner sc = new Scanner (System.in);
	    BufferedReader br=new BufferedReader(isr);
	    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
				System.out)));
		String str="";
		String res="";
		Scanner in = new Scanner(System.in);
		String [] sen = new String[100];
		int c=0,max=0,temp=0;
		int [] happy = new int [1000000];
		Arrays.fill(happy, -1);
		happy[1]=1;
		int [] val = {1,49,10,82,13,68,32,97,100,130};
		int [] it = {1,5,2,4,3,3,4,4,2,3};
		for (int i=2;i<=100000;i++) {
		}
		
		boolean flag=true;
		while (sc.hasNext()) {
			if (!flag) out.println();
			int L = sc.nextInt();
			int H = sc.nextInt();
			if (L==100) break;
			if (L>H) { 
				temp=L;
				L=H;
				H=temp;
			}
			
			for (int i=L;i<=H;i++) {
				int x=i,iter=0;
				while (x>100) {
					temp=0;
					while (x>0) {
						temp+=(x%10)*(x%10);
						x/=10;
					}
					x=temp;
					iter++;
				}
				temp=0;
				while (x>0) {
					temp+=(x%10)*(x%10);
					x/=10;
				}
				if (i!=1) iter++;
				for (int j=0;j<val.length;j++) {
					if (temp==val[j]) out.println(i+" "+(iter+it[j]));
				}
			}
			
			flag=false;
		}	
		
		out.close();
	}
	
}

[brianfry713]

What are you trying to accomplish with lines 29 and 30?
for (int i=2;i<=100000;i++) {
}

Why did you put this on line 37?
if (L==100) break;

[fohinni]

hey bishop..
i also did Uva 10591... and trying 944 with that method and i am getting WA..
so, what should i do to avoid WA ?