なぜこの再帰アルゴリズムは入力2,147,483,647に対して間違った答えを出すのですか？

Question

私は、次の質問に取り組んでいます：正の整数nを

を考えると、あなたは次のように操作を行うことができます。nが偶数の場合

• は、N/2のnを交換してください。
nが奇数の場合、あなたがn個に置き換えることができます
• のいずれかのn + 1またはn - 1

1になるためにn個のために必要な代替品の最小数は何ですか？

ここで私が思い付くしたコードです：入力が2147483647である場合には、私のコードが誤っ32.なぜ私のコードが間違った答えを与えている、正しい答えの代わりに33を出力

class Solution { 
private: 
    unordered_map<int, long long> count_num; 
public: 
    int integerReplacement(int n) { 
     count_num[1] = 0;count_num[2] = 1;count_num[3] = 2; 
     if(!count_num.count(n)){ 
      if(n%2){ 
       count_num[n] = min(integerReplacement((n-1)/2), integerReplacement((n+1)/2))+2; 
      }else{ 
       count_num[n] = integerReplacement(n/2) +1; 
      } 
     } 
     return(count_num[n]); 
    } 
}; 

は、ここに？

Answer 1

これは整数オーバフローと思われます。リストされた数値（2,147,483,647）は、符号付き32ビット整数を使用していると仮定してintに収まる最大値です。したがって、加算するとINT_MIN -2,147,483,648にオーバーフローします。そこから、あなたが間違った答えを得るのは驚くことではありません。なぜなら、この値はあなたが得ると期待した値ではないからです。もし

integerReplacement((n+1)/2) 

を計算しますので、計算するためにそのケースを修正する必要がありますとき

オーバーフローは、具体的に発生する（N + 1）オーバーフロー無し/ 2。これはかなり極端なケースなので、私はコードがそれに乗ったことに驚くことはありません。

これを行う1つの方法は、nが奇数の場合、（n + 1）/ 2が（n/2）+ 1（整数除算の場合）に等しいことに注意することです。だから、おそらくあなたは同じ値を計算しますが、オーバーフローを持っていない

integerReplacement((n/2) + 1) 

としてこれを書き換えることができます。