## 944 - Happy Numbers

Moderator: Board moderators

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 944 - Happy number

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 944 - Happy number

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

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

WA again and again

Code:

Code: Select all

``````import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
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 {
Scanner sc = new Scanner (System.in);
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.

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

### Re: 944 - Happy Numbers

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

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 ?