Home/

...

/

Happy numbers (medium)

Happy numbers (medium)

Resources for checking if a number is a happy number.

Dry-run templates

This is an implementation of the solution provided for the problem posed in the lesson:

Press + to interact
Python 3.5
def find_happy_number(num):
  slow, fast = num, num
  while True:
    slow = find_square_sum(slow)  # move one step
    fast = find_square_sum(find_square_sum(fast))  # move two steps
    if slow == fast:  # found the cycle
      break
  return slow == 1  # see if the cycle is stuck on the number '1'
def find_square_sum(num):
  _sum = 0
  while (num > 0):
    digit = num % 10
    _sum += digit * digit
    num //= 10
  return _sum
def main():
  print(find_happy_number(23))
  print(find_happy_number(12))
main()

Students may be encouraged to run through the provided solution with the following sample inputs. The while loop in the find_square_sum adds the squares of the digits of the number and returns the final sum. The sum column in the table below indicates the final number that is returned.

Sample input #1

Input: 23

Iteration

Line number

sum (slow)

slow

sum (fast)

fast

-

2

-

23

-

23

1

4

13

13

-

23

1

5

-

13

13

23

1

5

-

13

10

10

2

4

10

10

-

10

2

5

-

10

1

10

2

5

-

10

1

1

3

4

1

1

-

1

3

5

-

1

1

1

3

5

-

1

1

1

Sample input #2

Input: 12

Iteration

Line number

sum (slow)

slow

sum (fast)

fast

-

2

-

12

-

12

1

4

5

5

-

12

1

5

-

5

5

12

1

5

-

5

25

25

2

4

25

25

-

25

2

5

-

25

29

25

2

5

-

25

85

85

3

4

29

29

-

85

3

5

-

29

89

85

3

5

-

29

145

145

4

4

85

85

-

145

4

5

-

85

42

145

4

5

-

85

20

20

5

4

89

89

-

20

5

5

-

89

4

20

5

5

-

89

16

16

6

4

145

145

-

16

6

5

-

145

37

16

6

5

-

145

58

58

7

4

42

42

-

58

7

5

-

42

89

58

7

5

-

42

145

145

8

4

20

20

-

145

8

5

-

20

42

145

8

5

-

20

20

20

Step-by-step solution construction

The first step in our algorithm is the find_square_sum() function. The function returns a variable _sum with the sum of the squares of the given numbers.

The function returns a variable _sum with the square sum of the given number. For example, for 23, the _sum will be: 32+22=9+4=133^2 + 2^2 = 9 + 4 = 13.

Let’s visualise this function below:

Press + to interact
Python 3.5
def find_square_sum(num):
  _sum = 0
  i=1
  while (num > 0):
    print("Loop iteration: ", i)
    digit = num % 10
    print("Digit: ", digit)
    _sum += digit * digit
    print("Sum: ", _sum)
    num //= 10
    print("Updated number: ", num, "\n")
    i+=1
  return _sum
def main():
  input = [23, 12]
  for i in input:
    print("Input number: ", i, "\n")
    print("Sum of squares: ", find_square_sum(i))
    print("-"*100 + "\n")
main()

This code works as follows:

  • Line 6: Take modulus of the number with 10. This is to get the last digit of the input number.
  • Line 8: Add the square of the digit to the _sum.
  • Line 10: Divide the input number by 10 to remove the last digit of the number since we’ve already added the square of its value to _sum.

Now that we know how _sum is being calculated, let’s use it to run through the sum of squares sequence generated by a couple of input numbers:

Press + to interact
Python 3.5
def find_happy_number(num):
 slow, fast = num, num
 i=1
 while i < 11: # for now, let's calculate the sum of squares 10 times
   print("\tLoop iteration: ", i)
   print("\tSum returned: ", find_square_sum(slow))
   slow = find_square_sum(slow)  # move one step
   print("\tSlow: ", slow, "\n")
   i += 1
 return False # returning false for now, as solution is not complete
 
 
def find_square_sum(num):
 _sum = 0
 while (num > 0):
   digit = num % 10
   _sum += digit * digit
   num //= 10
 return _sum
 
 
def main():
 input = [12, 23]
 for i in input:
   print("Input number: ", i)
   print("is a happy number? ", find_happy_number(i))
   print("-"*100 + "\n")
 
 
 
main()

We initially set the slow pointer to num as shown in line 2. This is later updated by the value returned by the find_square_sum() function. Since we move the slow pointer by a factor of 1, the function is called only once per iteration.

Lastly, let’s see how the fast pointer is updated. Since it moves two steps each time, the find_square_sum function is called twice and the pointer is updated with the final _sum value returned. The initial value is set to the input number.

Press + to interact
Python 3.5
def find_happy_number(num):
 slow, fast = num, num
 # print("Fast: ", fast,"\n")
 i=1
 while i < 11: # for now, let's calculate the sum of squares 10 times
   print("\tLoop iteration: ", i)
   slow = find_square_sum(slow)  # move one step
   print("\tSlow:", slow)
   print("\tCalculating fast:\n\t\tSum returned by the first call:", find_square_sum(fast))
   print("\t\tSum returned by the second call:", find_square_sum(find_square_sum(fast)))
   fast = find_square_sum(find_square_sum(fast))  # move two steps
   print("\tFast:", fast)
   i+=1
 
 return False  # returning false for now, as solution is not complete
 
 
def find_square_sum(num):
 _sum = 0
 while (num > 0):
   digit = num % 10
   _sum += digit * digit
   num //= 10
 return _sum
 
 
def main():
 input = [12, 23]
 for i in input:
   print("Input number: ", i)
   print("is a happy number? ", find_happy_number(i))
   print("-"*100 + "\n")
 
 
main()

Line 10 can also be split into two separate function calls as:

fast = find_square_sum(fast)
fast = find_square_sum(fast)

Now that we know how our fast and slow pointers are being updated, the last step is to detect when we are in a cycle and to break out of the while loop at that point. Students may be encouraged to examine the output of the code above and note whether and when slow and fast become equal for the two inputs, 12 and 23.

If both slow and fast become 1, this means that the sequence converges to 1 and our input number is a happy number. However, if slow becomes equal to fast and they’re not 1, this implies that there is a cycle and our input number is not a happy number.

In the last step, we change the condition of the while loop to let it run forever but add a condition to break out of the loop when slow and fast become equal.

Press + to interact
Python 3.5
def find_happy_number(num):
 slow, fast = num, num
 print("Slow: ", slow)
 print("Fast: ", fast,"\n")
 i=1
 while True:
   print("Loop iteration: ", i)
   slow = find_square_sum(slow)  # move one step
   fast = find_square_sum(find_square_sum(fast))  # move two steps
   print("Slow: ", slow)
   print("Fast: ", fast, "\n")
   i+=1
   if slow == fast:  # found the cycle
     break
 if slow == 1 and fast == 1:
   print("Since both slow and fast are equal to 1,", num, "is a happy number!")
 else:
   print("Since slow and fast are equal, but not equal to 1, we've found a cycle.", num, "is not a happy number!")
 return slow == 1  # see if the cycle is stuck on the number '1'
 
 
def find_square_sum(num):
 _sum = 0
 while (num > 0):
   digit = num % 10
   _sum += digit * digit
   num //= 10
 return _sum
 
 
def main():
 input = [12, 23]
 for i in input:
   print("Input number: ", i)
   print("is a happy number? ", find_happy_number(i))
   print("-"*100 + "\n")
 
 
main()