Happy Number - LeetCode

浏览数：24 / 时间：2015年06月11日

examination questions

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

Example: 19 is a happy number

1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Please use the following function to solve the problem：

bool isHappy(int n) {

}

解题代码

#include <stdio.h>

bool isHappy(int n) {
    int arr[5000];
    int i = 0;
    int sum = 0;
    int temp1,temp2;

    while (true){
        do{
            temp1 = n / 10;
            temp2 = n % 10;
            n = temp1;
            sum = sum + temp2 * temp2;
        } while (temp1 > 0);

        if (sum != 1){
            arr[i] = sum;
            n = sum;
            i++;
        }
        else{
            return true;
        }
        for (int j = 1; j < i; j++){
            if (sum == arr[j-1]){
                return false;
            }
        }
        sum = 0;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    if (isHappy(n)){
        printf("true\n");
    }
    else{
        printf("false\n");
    }
    return 0;
}

LeetCode判断结果:

技术分享

基本算法思想

把一个数拆分成单个数, 然后进行平方和, 对和进行比较, 如果满足和为1, 就是快乐数, 如果进入循环, 那么就不是快乐数.

代码注释分析

#include <stdio.h>

bool isHappy(int n) {
    int arr[5000]; //用于存储和不为1的值,仅仅是猜想有这么多个值
    int i = 0; //记录和的个数
    int sum = 0; //和值
    int temp1, temp2; //temp1为值, temp2为余数

    while (true){
        do{
            temp1 = n / 10; 
            temp2 = n % 10;
            n = temp1; 
            sum = sum + temp2 * temp2; //和
        } while (temp1 > 0); //单个分解完成

        if (sum != 1){ //如果不为1,就把该和值赋值给arr
            arr[i] = sum;
            n = sum;
            i++;
        }
        else{
            return true;
        }
        for (int j = 1; j < i; j++){ //对和值进行循环匹配,如果和arr中的值相同,就退出,因为出现了循环
            if (sum == arr[j - 1]){
                return false;
            }
        }
        sum = 0;//第二次求和,必须先清零
    }
}

int main(){
    int n;
    scanf("%d", &n);
    if (isHappy(n)){
        printf("true\n");
    }
    else{
        printf("false\n");
    }
    return 0;
}

优化

经过资料查询, 对于快乐数, 有以下规律:

不是快乐数的数称为不快乐数（unhappy number），所有不快乐数的数位平方和计算，最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。

优化代码

#include <stdio.h>

bool isHappy(int n) {
    int sum = 0;
    int temp1, temp2;

    while (true){
        do{
            temp1 = n / 10;
            temp2 = n % 10;
            n = temp1;
            sum = sum + temp2 * temp2;
        } while (temp1 > 0);

        if (sum == 1){
            return true;
        }
        else{
            if (sum == 4 || sum == 20 || sum == 16 || sum == 37 || sum == 42 || sum == 58 || sum == 89 || sum == 145){
                return false;
            }
        }
        n = sum;
        sum = 0;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    if (isHappy(n)){
        printf("true\n");
    }
    else{
        printf("false\n");
    }
    return 0;
}