Solution to Leetcode - Happy Number
As part of 30 days challenge during the Covid-19 pandemic, Leetcode published this problem on the second day:
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.
Explanation
Happy Number = repeated sum of squares of digits will end in 1 Non Happy Number = repeated sum of squares will lead in an infinite loop.
Thought Process for Solution
The main task is to figure out when to stop out of the infinite loop and conclude that a number is not happy. Once you can figure this out, the code is not very tricky.
Let’s look at a sequence of a unhappy number, 42:
input = 42
=> 16 + 4 = 20
=> 4 + 0 = 4
=> 16 = 16
=> 1 + 36 = 37
=> 9 + 49 = 56
=> 25 + 36 = 61
=> 36 + 1 = 37
It’s evident from 37 that it will start to loop again from the 37 we have
already seen. This is important. We can now stop iterating because any number
of time we try 37, it’s going to give same sequence
37 -> 56 -> 61 -> 37 -> 56 -> ....
From here, the solution is simple, keep a track of already seen numbers and when ever a new number is found, add it to this set. We are good till the numbers are unique, but if we find a number we have already seen, that means we have detected a loop.
Pseudo Code
seen = {}
while number not in already seen and number is not 1:
find square of digits of number
add it to seen
Code
public class HappyNumber {
static boolean isHappy(int n) {
if (n <= 0) {
return false;
}
Set<Integer> alreadySeen = new TreeSet<>();
int current = n;
while (!alreadySeen.contains(current) && current != 1) {
alreadySeen.add(current);
current = squareOfDigits(current);
}
return current == 1;
}
static int squareOfDigits(int number) {
int[] digits = intToDigits(number);
return IntStream.of(digits).reduce(0, (a, b) -> a + b * b);
}
static int[] intToDigits(int number) {
return String.valueOf(number).chars().map(it -> it - '0').toArray();
}
}
Some test cases to validate
public class HappyNumberTest extends TestCase {
public void testIntToDigits() {
assertArrayEquals(new int[]{0}, HappyNumber.intToDigits(0));
assertArrayEquals(new int[]{1}, HappyNumber.intToDigits(1));
assertArrayEquals(new int[]{2}, HappyNumber.intToDigits(2));
assertArrayEquals(new int[]{1, 0}, HappyNumber.intToDigits(10));
assertArrayEquals(new int[]{2, 2}, HappyNumber.intToDigits(22));
assertArrayEquals(new int[]{9, 9}, HappyNumber.intToDigits(99));
assertArrayEquals(new int[]{1, 0, 0}, HappyNumber.intToDigits(100));
assertArrayEquals(new int[]{1, 0, 1}, HappyNumber.intToDigits(101));
assertArrayEquals(new int[]{5, 0, 0}, HappyNumber.intToDigits(500));
}
public void testSquareOfDigits() {
assertEquals(0, HappyNumber.squareOfDigits(0));
assertEquals(1, HappyNumber.squareOfDigits(1));
assertEquals(9, HappyNumber.squareOfDigits(3));
assertEquals(25, HappyNumber.squareOfDigits(5));
assertEquals(29, HappyNumber.squareOfDigits(25));
assertEquals(37, HappyNumber.squareOfDigits(16));
assertEquals(145, HappyNumber.squareOfDigits(89));
assertEquals(42, HappyNumber.squareOfDigits(145));
}
public void testIsHappy() {
assertTrue(HappyNumber.isHappy(1));
assertTrue(HappyNumber.isHappy(10));
assertTrue(HappyNumber.isHappy(100));
assertTrue(HappyNumber.isHappy(13));
assertTrue(HappyNumber.isHappy(31));
assertTrue(HappyNumber.isHappy(19));
assertFalse(HappyNumber.isHappy(25));
assertFalse(HappyNumber.isHappy(145));
assertFalse(HappyNumber.isHappy(41));
assertFalse(HappyNumber.isHappy(42));
assertFalse(HappyNumber.isHappy(0));
assertFalse(HappyNumber.isHappy(99));
assertFalse(HappyNumber.isHappy(573));
}
}
Conclusion
It’s an interesting problem with a very simple solution. Once you get the bright idea behind how to stop the loop, the solution becomes evident.