944 - Happy Numbers

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

Moderator: Board moderators

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 944 - Happy number

Post by Shafaet_du » Fri Jul 15, 2011 1:40 am

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.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 944 - Happy number

Post by plamplam » Sun Aug 28, 2011 2:06 pm

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 :wink:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 944 - Happy number

Post by Farsan » Thu Feb 06, 2014 6:02 am

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

sifatoooo
New poster
Posts: 1
Joined: Fri Oct 24, 2014 8:38 am

Re: 944 - Happy Numbers

Post by sifatoooo » Fri Oct 24, 2014 8:40 am

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();
	}
	
}
Last edited by brianfry713 on Fri Oct 24, 2014 9:18 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 944 - Happy Numbers

Post by brianfry713 » Fri Oct 24, 2014 9:29 pm

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;
Check input and AC output for thousands of problems on uDebug!

fohinni
New poster
Posts: 1
Joined: Tue Jan 26, 2016 9:46 pm

Re: 944 - Happy Numbers

Post by fohinni » Tue Jan 26, 2016 9:55 pm

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 ?

Post Reply

Return to “Volume 9 (900-999)”