এই সমস্যায়, আমাদের n সংখ্যার অ্যারে দেওয়া হয়েছে। এবং এখানে দুইজন খেলোয়াড় X এবং Y আছে। আমাদের কাজ হল গেমের বিজয়ীর ভবিষ্যদ্বাণী করা।
প্লেয়ার X-এর জন্য X এবং Y দ্বারা সংখ্যার যোগফলের পরম পার্থক্য 4-এর গুণিতক হওয়া উচিত। যদি এটি 4 দ্বারা বিভাজ্য না হয়, তাহলে Y জিতবে। প্লেয়ার X খেলা শুরু করে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
Input: a[] = {3 6 9 12}
Output: X
Explaination:
X selects 3 and 6
Y selects 12 and 9
|3+6 - 12+9| = 12, 12 is a multiple of 4. এই সমস্যাটি সমাধান করার জন্য, আমরা অ্যারের প্রতিটি উপাদান 4 দ্বারা বিভাজ্য কিনা তা পরীক্ষা করব এবং একটি সংখ্যাকে 4 দ্বারা ভাগ করার সময় পাওয়া অবশিষ্টাংশের উপর নজর রাখব। যদি প্রতিটি অবশিষ্টাংশের উপস্থিতি জোড় হয়, তাহলে X জয়ী হয়। অর্থাৎ পরম পার্থক্য 4 দ্বারা বিভাজ্য।
প্রতিটি মানের জন্য arr[i]%4 এর সংখ্যা 0, 1, 2 ,3 সমান হওয়া উচিত।
আমাদের অ্যালগরিদমের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
int playGame(int a[], int n) {
int count[4] = {0,0,0,0};
for (int i = 0; i < n; i++) {
for(int j = 0; j<4;j++){
if(a[i]%4 == j)
count[j]++;
}
}
if (count[0] % 2 == 0 && count[1] % 2 == 0 && count[2] % 2 == 0 && count[3] == 0)
return 1;
else
return 2;
}
int main() {
int a[] = { 4, 8, 5, 9 };
int n = sizeof(a) / sizeof(a[0]);
cout<<"Game Started!\n";
if (playGame(a, n) == 1)
cout << "X wins the Game";
else
cout << "Y wins the Game";
return 0;
} আউটপুট
Game Started! X wins the Game
