快速找到不愉快的號碼

Question

我試圖解決一個問題。給定一系列的整數，用戶必須找到給定範圍內不滿的數量。

Unhappy number - 一個數n，使得這個迭代平方加總，數字地圖開始有n從未達到1

我通過計算平方和使用蠻力方法嘗試數的數字，並且如果在任何時候它等於這些中的任何一個（4,16,37,58,89,145,42,20），那麼它是不幸的數字。

這種方法是給TLE有沒有更好的方法？

範圍在1到10^18之間。

Answer 1

#include <map> 
#include <set> 

bool happy(int number) { 
    static std::map<int, bool> cache; 

    std::set<int> cycle; 
    while (number != 1 && !cycle.count(number)) { 
     if (cache.count(number)) { 
      number = cache[number] ? 1 : 0; 
      break; 
     } 
     cycle.insert(number); 
     int newnumber = 0; 
     while (number > 0) { 
      int digit = number % 10; 
      newnumber += digit * digit; 
      number /= 10; 
     } 
     number = newnumber; 
    } 
    bool happiness = number == 1; 
    for (std::set<int>::const_iterator it = cycle.begin(); 
    it != cycle.end(); it++) 
    cache[*it] = happiness; 
    return happiness; 
} 

#include <iostream> 

int main() { 
    for (int i = 1; i < 10; i++) 
     if (!happy(i)) 
     std::cout << i << std::endl; 
    return 0; 
} 

輸出：

2 
3 
4 
5 
6 
8 
9 

邏輯與大多數從這裏取出的代碼：https://tfetimes.com/c-happy-numbers/

Answer 2

你的範圍是在1和10 之間。這意味着您的號碼最多有18位數字。

考慮到一個數字的最大正方形是9 = 81，做平方位求和一次的最大數目爲18 * 81 = 1458

所以一個平方位求和後加上1500個元素的查找表就足夠了。

或兩個方形的數字和數加上〜330元的查找表：

static const bool unhappy[330] { 
    1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1, 
    1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1, 
    1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1, 
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1, 
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1, 
    0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1, 
    1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1, 
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1, 
    1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0 
} 

inline bool is_unhappy(uint64_t n) { 
    while (n >= 330) { 
     int r = 0; 
     while (n > 0) { 
      int d = n % 10; 
      r += d*d; 
      n /= 10; 
     } 
     n = r; 
    } 

    return unhappy[n]; 
}