समस्या कथन
N राक्षसों को देखते हुए, प्रत्येक राक्षस का प्रारंभिक स्वास्थ्य h[i] होता है जो एक पूर्णांक होता है। एक राक्षस जीवित है यदि उसका स्वास्थ्य 0 से अधिक है।
प्रत्येक मोड़ में एक यादृच्छिक राक्षस दूसरे यादृच्छिक राक्षस को मारता है, जिस राक्षस पर हमला किया जाता है, उसका स्वास्थ्य हमलावर राक्षस के स्वास्थ्य की मात्रा से कम हो जाता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि एक भी राक्षस न रह जाए। अंतिम बचे हुए राक्षस का न्यूनतम संभव स्वास्थ्य क्या होगा।
उदाहरण
यदि इनपुट ऐरे {2, 14, 28, 56} है तो आउटपुट 2 होगा क्योंकि जब केवल पहला राक्षस शेष 3 राक्षसों पर हमला करता रहेगा, तो अंतिम राक्षस का अंतिम स्वास्थ्य 2 होगा, जो न्यूनतम है।
एल्गोरिदम
हम नीचे दिए गए GCD सूत्र का उपयोग करके अंतिम उत्तर प्राप्त कर सकते हैं -
एच(मिनट) =जीसीडी(एच1, एच2,…, एचएन)
उदाहरण
#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