loading...

The Happy Number Problem

alisabaj profile image Alisa Bajramovic Updated on ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

In this post I'll be walking through the Happy Number Algorithm, a problem recently featured on Leetcode's 30 Day Challenge in April (you can find the problem here).

Here's the question:

Write an algorithm to determine if a number n 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.

Return True if n is a happy number, and False if not.

For example, let's say your input was 19. The expected output would be true. 19, when broken down into its digits, is 1 and 9. Those numbers squared are 1 and 81. 1 + 81 is 82. 82 broken into its digits is 8 and 2. Those numbers squared are 64 and 4, and 64 + 4 = 68. 68 broken down into its digits is 6 and 8. Those numbers squared is 36 and 64. 36 + 64 = 100. 100 broken down into its digits is 1, 0, and 0. Those numbers squared and summed is 1, which makes it a happy number.

There are a number of ways to approach this problem, and in this post I'll be walking through how to use recursion to solve it.

The first thing I'll do is initialize a variable called sum. The digits of a number will be broken up, set to the power of two, and then added, so it's important to keep track of what the sum is.

function isHappy(n) {
  let sum = 0;
  //...
}

Then, I'll want to break up a number using modulo. As I've explained in a previous blog post, when asked to manipulate a number, it's best to do so without changing it to a string or integer. Modulo enables you do to this easily. If given n = 25, n%10 would give you the result of 5, and n would be 20. Then, we'll want to divide n by 10 in order to shift the digits over. We'll keep doing this as long as n is greater than 0. The other thing to do in this while loop is to add the square of each result of the modulo to the sum. Written out, the function now looks like this:

function isHappy(n) {
  let sum = 0;
  while (n > 0) {
    let e = n % 10;
    n = Math.floor(n / 10);
    sum += e * e;
  }
  //...
}

Now, we need to check what the sum is. If the sum is equal to 1, then it's a happy number, and we can return true.

function isHappy(n) {
  let sum = 0;
  while (n > 0) {
    let e = n % 10;
    n = Math.floor(n / 10);
    sum += e * e;
  }
  if (sum === 1) {
    return true;
  }
  //...

If the sum is greater than 1 but less than or equal to 4, then we know the sum will get stuck in an infinite loop and will never equal 1, so it's definitely not a happy number. You can test this out yourself: if the number is 2, then 2^2 is 4. 4^2 is 16. 1^2 + 6^2 = 37. 3^2 + 7^2 = 58. 5 ^2 + 8^2 = 89. 8^2 + 9^2 = 145. 1^2 + 4^2 + 5+2 = 42. 4^2 + 2^2 = 20. 2^2 + 0^2 = 4 -- and we're stuck in the same loop. (You can also try this out for 3). Therefore, if the sum is greater than 1 and less than or equal to 4, then we can return false.

function isHappy(n) {
  let sum = 0;
  while (n > 0) {
    let e = n % 10;
    n = Math.floor(n / 10);
    sum += e * e;
  }
  if (sum === 1) {
    return true;
  } else if (sum > 1 && sum <= 4) {
    return false;
  }
  //...
}

The final thing to do is make a recursive call to the function. If the sum does not fulfill one of the base cases--it's not equal to 1, 2, 3, or 4--then its digits need to be split, squared, and summed, therefore calling the function again. Therefore, we need to call the function, this time with sum as the argument. It's also important to write 'return' before the function call, or else you'll end up with a result of 'undefined', since nothing was returned back.

function isHappy(n) {
  let sum = 0;
  while (n > 0) {
    let e = n % 10;
    n = Math.floor(n / 10);
    sum += e * e;
  }
  if (sum === 1) {
    return true;
  } else if (sum > 1 && sum <= 4) {
    return false;
  }
  return isHappy(sum);
}

And that's it! Feel free to leave alternate solutions or questions in the comments.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

Your solution makes sense, mathematically.
However, I think it's a wasted chance to use and explain recursion with carryover.
The function can be something like this:

function isHappy(n, seenSums = []) {
  // ... same as above
  if (sum === 1) return true; // answer found
  if (seenSums.includes(sum)) return false; // generic infinite loop detection mechanism
  return isHappy(sum, seenSums.concat([sum])); // recursion with carryover
}
 

You could use Set instead of an array for seenSums, that way your validation to check the infinite loop could be done in constant time by changing

  if (seenSums.includes(sum)) return false; // generic infinite loop detection mechanism

for

  if (seenSums.has(sum)) return false; // generic infinite loop detection mechanism
 

Why aren't you adding the square of n to the sum?

 

I'm dividing n into it's digits (so 19 becomes 1 and 9) and then adding the square of those numbers to the sum.

 

Yeah I got that, but I don't see sum += n*n anywhere

The line 'sum += e * e' is what sums the digits

Ahh, I missed the while loop there. Oops