C++でのゲームの最後のモンスターの可能な最小の最終的な健康状態

問題の説明

N個のモンスターが与えられると、各モンスターの初期体力h[i]は整数になります。体力が0より大きい場合、モンスターは生きています。

各ターンで、ランダムモンスターは別のランダムモンスター、攻撃されたモンスターを殺し、その体力は攻撃しているモンスターの体力の量だけ減少します。このプロセスは、モンスターが1体残るまで続けられます。最後に残ったモンスターの可能な最小の健康状態はどうなりますか。

例

入力配列が{2、14、28、56}の場合、最初のモンスターだけが残りの3つのモンスターを攻撃し続けると、最後のモンスターの最終的な体力は2になり、最小であるため、出力は2になります。

アルゴリズム

以下のGCD式を使用して最終的な答えを得ることができます-

H（min）=gcd（h1、h2、…、hn）

例

#include <iostream>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
   return b;
   return gcd(b % a, a);
}
int getPossibleHealth(int* health, int n) {
   int currentGcd = gcd(health[0], health[1]);
   for (int i = 2; i < n; ++i) {
      currentGcd = gcd(currentGcd, health[i]);
   }
   return currentGcd;
}
int main() {
   int health[] = { 4, 6, 8, 12 };
   int n = sizeof(health) / sizeof(health[0]);
   cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Possible final health = 2