সমস্যা বিবৃতি
N দানব দেওয়া, প্রতিটি দানবের প্রাথমিক স্বাস্থ্য h[i] থাকে যা একটি পূর্ণসংখ্যা। একটি দানব বেঁচে থাকে যদি তার স্বাস্থ্য 0-এর বেশি হয়।
প্রতিটি পালাক্রমে একটি এলোমেলো দানব আরেকটি এলোমেলো দানবকে হত্যা করে, যে দানবটি আক্রমণ করা হয়, আক্রমণকারী দৈত্যের স্বাস্থ্যের পরিমাণ দ্বারা তার স্বাস্থ্য হ্রাস পায়। একটি একক দানব বাকি না হওয়া পর্যন্ত এই প্রক্রিয়াটি অব্যাহত থাকে। শেষ রয়ে যাওয়া দানবের ন্যূনতম সম্ভাব্য স্বাস্থ্য কী হবে।
উদাহরণ
যদি ইনপুট অ্যারে হয় {2, 14, 28, 56} তাহলে আউটপুট হবে 2 কারণ যখন শুধুমাত্র প্রথম দানবটি বাকি 3টি দানবকে আক্রমণ করতে থাকে, তখন শেষ দানবের চূড়ান্ত স্বাস্থ্য 2 হবে, যা সর্বনিম্ন।
অ্যালগরিদম
আমরা নিচের GCD সূত্র −
ব্যবহার করে চূড়ান্ত উত্তর পেতে পারিH(মিনিট) =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
