Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Happy Number (medium)

Problem Statement

Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to the number 1. All other (not-happy) numbers will never reach 1. Instead, they will be stuck in a cycle of numbers that does not include 1.

Given a positive number n, return true if it is a happy number otherwise return false.

Example 1:

Input: 23
Output: true (23 is a happy number)
Explanations: Here are the steps to find out that 23 is a happy number:

2^2 +3^2 = 4 + 9 = 13

.....

.....

.....

Like the course? Get enrolled and start learning!
H

hj3yoo

· 4 years ago

The time complexity analysis seems incomplete. It only analyses the time it takes to calculate the next sequence number (sure, that time is bound to get smaller over iteration, but the analysis doesn't mention it).

I would recommend looking at the Leetcode solution for more detailed analysis: https://leetcode.com/problems/happy-number/solution/

Some Dude

Some Dude

· 3 years ago

The question gives no constraints about the input being a positive number, and -1 will immediately go to a sum of 1.

A

Aidan Eglin

· 4 years ago

Would a solution involving hashmaps and recursion not also be valid?

let happyMap = {};

function happyNumber(number) {

if (happyMap[number] != undefined) return false;

reduction = number.toString().split("").map(x => parseInt(x)**2).reduce((acc, current, index) => { return acc + current; }, 0);

happyMap[number] = reduction;

if (reduction == 1) return true;

return happyNumber(reduction);

}

Show 3 replies
Cady Shelhon

Cady Shelhon

· 3 years ago

When you do -1^2, that will equal 1 and therefore should return true. Should there be a constraint in the question stating that only positive numbers are happy?

Show 2 replies
M

maagjoel1

· 3 years ago

I am struggling to understand the time complexity of this solution. Specifically with why M = log(N +1). Where does this come from?

Show 2 replies
anhquan.tranle0601

anhquan.tranle0601

· 3 years ago

If num = 10, in the loop body the condition slow == fast will be true and the function return False, which is incorrect.

We should have a condition to check if fast == 1 before checking slow == fast

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from math import pow

class Solution:

  def find(self, num):

    def digits_square_sum(num):
      digits = []
      while num > 0:
        digits.append(num % 10)
        num = num // 10
      square_sum = 0
      for digit in digits:
        square_sum += pow(digit, 2)
      return square_sum

    slow = digits_square_sum(num)
    fast = digits_square_sum(digits_square_sum(num))

    while slow != 1 and fast != 1:
      slow = digits_square_sum(slow)
      fast = digits_square_sum(digits_square_sum(fast))
      if fast == slow:
        return False

    return True
Douglas McDonald

Douglas McDonald

· 2 years ago

I understand how a two-pointer solution to this would work, but I don't understand why it's considered optimal over a hashmap recursion approach. Here's my understanding:

HASHMAP:

Create an empty hashmap. Call a function to check next happy number. If result == 1, return true. Else if result exists in hashmap, return false. Else, push result to hashmap and recurse with result.

Ultimately, this should loop through every "node" in the "linked list" exactly once and the hashmap will contain every unique "node" in the linked list. Therefore, where n = # of "nodes", Time complexity = O(n), space complexity = O(n)

TWO-POINTER:

Create two "pointers" and assign initial value for both While they don't equal each other and fastpointer doesn't equal 1, call a function to check next happy number

Show 1 reply
Nabeel Keblawi

Nabeel Keblawi

· 2 years ago

I wasn't sure how to use two pointers to solve this problem. So I took a different approach. I created a list to store all the sums calculated until a repeating sum was found, in which case is the beginning of a repetitive cycle.

Here's what I did:

class Solution:
  def find(self, num):
    # Initialize the current sums variable and an empty list to keep track of all sums
    ssum = num
    list_ssums = []

    # Repeat this block as long as the sum isn't being repeated (not found in list_ssums)
    while ssum not in list_ssums:
      list_ssums.append(ssum)
      digits = self.num_split(ssum)
      ssum = self.calc_squares(digits)
      if ssum == 1:
        return True   # Base case: return True if 1 is found
    return False      # If any sum repeats itself, break and r
Show 1 reply
Luis Roel

Luis Roel

· 2 years ago

def isHappy(self, n: int) -> bool:
    # The first sum is the inpout
    curr_sum = n
    # We keep track of cycles using a set
    seen = set()
    
    # The goal is to see if we can reach a sum
    # of 1 or, notice if we've seen a particular sum
    # before
    while curr_sum != 1 and curr_sum not in seen:
        # First, add current sum to our set before we change it
        seen.add(curr_sum)
        
        # Get the digits of current sum
        digits = [int(d) for d in str(curr_sum)]
        
        # Calculate new sum
        # (notice we're starting fresh, not adding to curr_sum)
        new_sum = 0
        for digit in digits:
            # Square the current digit and
            # add it to the new sum
            new_sum += digit * digit
            
        #