-
Notifications
You must be signed in to change notification settings - Fork 0
/
Happy Number
76 lines (66 loc) · 3.24 KB
/
Happy Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/* Programmer : Dhruv Patel
* Problem Name : Happy Number
* Used In : Leetcode
* Used As : 202
* Problem :
* Write an algorithm to determine if a number is "happy".
* A happy number is a number defined by the following process: Starting with any positive integer,
* replace the number by the sum of the squares of its digits, and repeat the process until the number
* equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
* Those numbers for which this process ends in 1 are happy numbers.
* Example : 19 is a happy number
* 1^2 + 9^2 = 82
* 8^2 + 2^2 = 68
* 6^2 + 8^2 = 100
* 1^2 + 0^2 + 0^2 = 1
* Credits:
* Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.
* Thoughts =>
* Brute Force / Naive Approach :-
*
*/
import java.util.HashSet;
import java.util.Set;
class Solution {
static Set<Integer> set = new HashSet<>(); // Dictionary to compute each result
public static int reduce(int x) {
while (x > 9) { // We keep normalizing number while it's > 9
String test = Integer.toString(x);
int counter = 0;
for (char c : test.toCharArray()) {
if (Character.getNumericValue(c) > 0) {
counter += (Character.getNumericValue(c) * Character.getNumericValue(c)); // We count square of each digit and skipping 0
}
}
return reduce(counter);
}
return x;
}
public static boolean isHappy(int n) { // isHappy returns boolean for magic test
if (set.contains(n)) {
return false;
}
set.add(n);
while (n >= 1) {
int f = n % 10; // f holds the remainder
int s = n / 10; // s holds the divider
if (f > 9) {
f = reduce(f); // Reducing the number if its > 9
}
if (s > 9) {
s = reduce(s);
}
if (f + s == 1) {
return true; // We return true if it's sum is 1.
}
return isHappy((f * f) + (s * s)); // Else we keep looking for its squares.
}
return false; // False if while loop terminates and sum is not 1
}
public static void main(String args[]) {
int i = 0;
while (i <= Integer.MAX_VALUE) {
System.out.println(isHappy(i++));
}
}
}