whileループを終えるときの条件がわからない。

Question

#質問文↓と実行しているコードに差があることでエラーが起こっていると思うのですが、whileループを終える条件は、n==1の時と、どの時ですか？

###解決したコード

class Solution {
public:
    bool isHappy(int n) {
        int remain;
        int sum=0;
        
        
        while(n>9){
            while(n){
                remain=n%10;
                sum+=remain*remain;
                n=n/10;
            }
            n=sum;
            sum=0;
        }
         
        if(n==1)
            return true;
        else if(n==7)
            return true;
        else
            return false;
    }
};

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

Return True if n is a happy number, and False if not.

###コード

class Solution {
public:
    bool isHappy(int n) {
        
        bool isone=false;
        bool ishun=false;
        bool isten=false;
        int one;
        int ten;
        int hun;
         
        while(n!=1){ //←この条件を何にすべきかわかりません。
            isone=false;
            ishun=false;
            isten=false;
            
            if(n<10)
                isone=true;
            
            else if(n<100){
                isone=false;
                isten=true;
            
            }else if(n>99){
                isten=false;
                ishun=true;
            }     
            
            if(isone){
                one=n;
                n=one*one;
                 
            }else if(isten){
                ten=n/10;
                one=n-ten*10;
                
                n=ten*ten+one*one;
            }else if(ishun){
                hun=n/100;
                ten=(n-hun*100)/10;
                one=n-hun*100+ten*10;
                
                n=hun*hun+ten*ten+one*one; //←エラーはここにあります。
            }
       }
        if(n==1)
            return true;
        else
            return false;
    }
};

###エラー

Line 66: Char 22: runtime error: signed integer overflow: 231813 * 231813 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:75:22

Comments

[yumetodo]

とりあえずintじゃなくてuint64_tに変えてみてはどうですかね？エラー文そのものは型の大きさが足らんって言ってるので

[alizona]

ありがとうございます。
uint64_t ですね。初めて見ました。

使い方等理解したのですが、
私の解く問題の関数の引数の型は予めintに指定されています。
英語が読めてなくて、whle loopの条件をどうしていいかわかっていません。
そのため桁数が大きくなるまでループして、今回のエラーが起こっています。

Answer 1

１以外の脱出条件は、以下↓に書いてあります。
ハッピー数を知ってハッピーに！

また、ウィキペディアには、Pythonのプログラムが出ています。

Comments

[cateye]

・・・１０進１桁の２乗ですから、８１（９×９）より大きくは絶対なりません。

[alizona]

無限リピートだった時の脱出について書かれているということでしょうか？

[cateye]

引用ーー＞
あれ？また４にもどりましたね。
このまま続けても繰り返しになるので４は１になることはありません。
つまり、「４はハッピー数ではない」ということが言えます。
＜ーーーここまでが、脱出条件です。
あるいは・・・
while (n > 1) and (n not in s):・・・１以上かつ『今まで出てない数値』の間ループ
分かりますか？

[alizona]

理解できたと思います。ありがとうございます。

Answer 2

根本原因はそこじゃないです。
処理方法が全く間違っています。全面的に考え直しましょう。
質問文の方法では計算過程の合計が一時的にでも100を超えると破綻します。

ヒントは、

• nを10で割った余りを出すとnの一番下の桁の数字が取得できる
• nを10で割る（小数点未満切り捨て）と桁を１つ繰り下げることができる

終了条件については、n==1なら成功ですが、もしいつまでたってもnが1にならなければ無限ループです。
計算結果はnに対して一意に決まるので、計算過程で出てくるnを記録して同じ値が出現したら無限に続くとみなせるかと思います。

Comments

[hope_mucci]

なお、質問のコードはn=2で早くも破綻します。

[hope_mucci]

自分で作った検証プログラムが間違ってました。並びに不適切な内容を修正しました。申し訳ない。

[alizona]

お礼の返信遅くなり申し訳ありません。
1時間ほど、考えたり、サンプルを調べたりしていたのですが、まだ理解できなく、今2amなので、明日起きてからやることにしました。あまりを使った考え方は理解しました。明日は、10でわるというとこから考えたいと思います。

[alizona]

遅くなりました。全て理解することができました。
ありがとうございました。
コードは、質問の下あたりに足しておきます。

Answer 3

エラーの原因
one=n-hun100+ten10;
10の桁を加算しているので、1の桁の数字となりません。

whileループを終える条件
永久ループになる場合に終了 ⇔ 過去のnと一致した、を追加する必要があると思います。

Comments

[alizona]

it loops endlessly in a cycle which does not include 1.

という質問文では、永久ループの場合に終了するということを行っていたのですね。
そして、どのようにして永久ループと判断するかというと、過去のnを保管して、一致したかどうかを確認するということでしょうか？

[YT0014]

過去のnと一致する＞その次の値は、過去のnの次の値＞...となり、同じ回数の処理で、また、そのnと一致します。
なお、hope_mucciさんのご指摘の、各桁の数字の取得方法改善や桁数制限もご検討ください。剰余演算子を検索してみてください。

[alizona]

ありがとうございます。