[Algorithm] Happy Number

Happy Number

Problem statement:

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

• 12 + 92 = 82
  
• 82 + 22 = 68
  
• 62 + 82 = 100
  
• 12 + 02 + 02 = 1
  

Solution 1 : Naive Approach (not bad though) 

For this problem a naive approach will perform this transformation of the number and keep track of visited number in a hashset. If we ever visited this number we break out of the loop and check if the repeating number is 1.

Code implementation:

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

class Solution { public: bool isHappy(int n) { set<int> history; int curr = n; while (true) { int next = 0; while (curr) { int d = curr%10; next += d * d; curr /= 10; } if (next == 1) return true; if (history.count(next) == 0) { history.insert(next); } else { break; } curr = next; } return false; } };

Solution 2: Loop Detection

Based on the naive approach, we can improve by not using the hashset. Imagine we have all the numbers we come across during the transformation as a linked list. Assume the linked list will have a loop and our goal is to find where the loop overlaps.

For example:

48 -> 80 -> 64 -> 52 -> 29 -> 85 -> 89 -> 145 -> 48

We don't need to find out where the loop starts because if the loop starts with 1 it will stuck at 1, in other words, if we break out of the loop by detected a loop we just need to check wether the number we have is 1 or not.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: bool isHappy(int n) { int slow = next(n); int fast = next(next(n)); while(slow != fast) { slow = next(slow); fast = next(next(fast)); } return (slow == 1); } int next(int n) { int sum = 0; while(n) { sum += pow(n%10, 2); n /= 10; } return sum; } };