▼

LintCode: Happy Number 快樂數

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 https://www.lintcode.com/problem/happy-number/description。

這題也不會很困難，從Wiki的說明：

快樂數有以下的特性：在給定的進位制下，該數字所有數位(digits)的平方和，得到的新數再次求所有數位的平方和，如此重複進行，最終結果必為1。
例如，以十進位為例：
2 8 → 22+82=68 → 62+82=100 → 12+02+02=1
3 2 → 32+22=13 → 12+32=10 → 12+02=1
3 7 → 32+72=58 → 52+82=89 → 82+92=145 → 12+42+52=42 → 42+22=20 → 22+02=4 → 42=16 → 12+62=37

28和32是快樂數，而37不是，底下附上筆者的解法。

 
 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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int square(int x) {
        return x * x;
    }

    int happy(int n) {
        int sum = 0;
        int digit;

        digit = n % 10;
        sum += square(digit);
        n = n / 10;

        while( n > 0 ) {
            digit = n % 10;
            sum += square(digit);
            n = n / 10;
        }
        
        return sum;
    }

    /**
     * @param n an integer
     * @return true if this is a happy number or false
     */
    bool isHappy(int n) {
        // Write your code here
        if (n == 1)
            return true;
        else if ( n == 4 )
            return false;
        else
            return isHappy(happy(n));
    }
};

沒有留言:

張貼留言