ধরুন আমাদের একটি অ্যারে আছে যেখানে 1 থেকে n পর্যন্ত এলোমেলো ক্রমে n উপাদান রয়েছে। আরেকটি পূর্ণসংখ্যা K দেওয়া আছে। সেখানে এন জনগণ ব্যাডমিন্টন খেলতে এক কাতারে দাঁড়িয়ে আছে। প্রথম দুই খেলোয়াড় খেলার জন্য যাবে, তারপর পরাজিত ব্যক্তি গিয়ে সারির শেষে বসবে। বিজয়ী সারি থেকে পরবর্তী ব্যক্তির সাথে খেলবে ইত্যাদি। তারা খেলবে যতক্ষণ না কেউ পরপর K বার জিতছে। তারপর সেই খেলোয়াড় বিজয়ী হয়।
যদি সারিটি [2, 1, 3, 4, 5] এবং K =2 এর মত হয়, তাহলে আউটপুট হবে 5। এখন ব্যাখ্যাটি দেখুন −
(2, 1) নাটক, 2 জয়, তাই 1 সারিতে যোগ করা হবে, সারির মত [3, 4, 5, 1] (2, 3) নাটক, 3 জয়, তাই 2টি সারিতে যোগ করা হবে, সারি হল [4, 5, 1, 2] (3, 4) নাটক, 4 জয়, তাই 3টি সারিতে যোগ করা হবে, সারি হল [5, 1, 2, 3] (4, 5) নাটকের মতো, 5টি জয়, তাই 4টি সারিতে যোগ করা হবে, সারিটি হল [1, 2, 3, 4] (5, 1) নাটকের মতো, 5টি জয়, তাই 3টি সারিতে যোগ করা হবে, সারির মতো [2, 3] , 4, 1]
(2, 1) নাটক, 2 জয়, তাই সারিতে 1 যোগ করা হবে, সারির মতো [3, 4, 5, 1]
(2, 3) নাটক, 3 জয়, তাই সারিতে 2 যোগ করা হবে, সারির মত [4, 5, 1, 2]
(3, 4) নাটক, 4 জয়, তাই 3টি সারিতে যোগ করা হবে, সারির মতো [5, 1, 2, 3]
(4, 5) নাটক, 5 জয়, তাই 4টি সারিতে যোগ করা হবে, সারির মতো [1, 2, 3, 4]
(5, 1) নাটক, 5 জয়, তাই 3টি সারিতে যোগ করা হবে, সারির মতো [2, 3, 4, 1]
যেহেতু 5 টানা দুই ম্যাচ জিতেছে, তাহলে আউটপুট হল 5।
অ্যালগরিদম
বিজয়ী(arr, n, k)
Begin if k >= n-1, then return n best_player := 0 win_count := 0 for each element e in arr, do if e > best_player, then best_player := e if e is 0th element, then win_count := 1 end if else increase win_count by 1 end if if win_count >= k, then return best player done return best player End
উদাহরণ
#include <iostream>
using namespace std;
int winner(int arr[], int n, int k) {
if (k >= n - 1) //if K exceeds the array size, then return n
return n;
int best_player = 0, win_count = 0; //initially best player and win count is not set
for (int i = 0; i < n; i++) { //for each member of the array
if (arr[i] > best_player) { //when arr[i] is better than the best one, update best
best_player = arr[i];
if (i) //if i is not the 0th element, set win_count as 1
win_count = 1;
}else //otherwise increase win count
win_count += 1;
if (win_count >= k) //if the win count is k or more than k, then we have got result
return best_player;
}
return best_player; //otherwise max element will be winner.
}
main() {
int arr[] = { 3, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << winner(arr, n, k);
} আউটপুট
3
