Sunday, September 26, 2010

Happy number

As reminder, a happy number is the number where the sequence of the sum of the squares of the digits equal 1.
For example, 1 is happy number because 12 = 1. 


7 is  a happy number because 
  72 = 49
  42 + 92 = 97
  92 + 72 = 130
  12 + 32 + 02 = 10
  12 + 02 = 1.


4 is not a happy number because

  42 = 16
  12 + 62 = 37
  32 + 72 = 58
  52 + 82  = 89
  82 + 92 = 145
  12 + 4+ 52  = 42
  4+ 2 = 20
  2+ 0 = 4








that yields an infinite loop digit sum of squares.
Here is my attempt to write happy number in Scala way.
First, I need to define sumOfSquares function, implemented as follow:

 1 def sumOfSquares(n: Int): Int = {
 2   def sumOfSquares(n: Int, powOf10: Int, acc: Int): Int = {
 3     if ( n / powOf10 == 0) {
 4       acc
 5     }
 6     else {
 7       val digit = (n / powOf10) % 10
 8       val result = acc + digit * digit 
 9       sumOfSquares(n, powOf10 * 10, result)
10     }
11   }
12   sumOfSquares(n, 1, 0)
13 }
14     

The function calls an inner method sumOfSquares that is a recursive function, taking into account that the sumOfSquares of an integer is the square of its last digit + the sumOfSquares the rest of the digits. 
The isHappyNumber function is then defined as follow:



14
15 def isHappyNumber(n: Int) = {
16   def isHappyNumberList(n: Int, lst: Set[Int]): Boolean = {
17     sumOfSquares(n) match {
18       case 1 => true
19       case sum => !lst.contains(sum) && isHappyNumberList(sum, lst + n)  
20     }
21   }
22   isHappyNumberList(n, Set.empty)
23 }
24 


That is, if the sum of squares of n is 1, then n is a happy number, otherwise n is a happy number when its sum of squares is a happy number given the sequence of the sum of squares does not yield an infinite loop.
To detect an infinite loop, a set of calculated sum of squares is kept and for each new generated sum, the program verifies that the number is not in the set already.

No comments: