एकल चालों का उपयोग करके k द्वारा ऐरे तत्व को स्थानांतरित किया गया?

मान लीजिए कि हमारे पास एक सरणी है जिसमें शफल क्रम में n तत्व 1 से n तक हैं। एक और पूर्णांक K दिया गया है। वहाँ N लोग हैं जो बैडमिंटन खेलने के लिए एक कतार में खड़े हैं। पहले दो खिलाड़ी खेलने के लिए जाएंगे, फिर हारने वाला जाकर कतार के अंत में जाएगा। विजेता कतार से अगले व्यक्ति के साथ खेलेगा वगैरह। वे तब तक खेलेंगे जब तक कोई लगातार 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);
}