Sponsored
Sponsored
This approach involves simulating the game as described. In each round, compare the first two elements. The larger element stays at the front, while the smaller one is moved to the end. Track the number of consecutive wins for the current maximum element. The game terminates once an element wins k consecutive games, or we can conclude the maximum element will always win once it has dominated for enough rounds due to its magnitude relative to other elements.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) as we use only constant space.
1#include <stdio.h>
2
3int getWinner(int* arr, int arrSize, int k) {
4 int max = arr[0];
5 int win_count = 0;
6 for (int i = 1; i < arrSize; ++i) {
7 if (max > arr[i]) {
8 win_count++;
9 } else {
10 max = arr[i];
11 win_count = 1;
12 }
13 if (win_count == k)
14 return max;
15 }
16 return max;
17}
18
19int main() {
20 int arr[] = {2, 1, 3, 5, 4, 6, 7};
21 int k = 2;
22 int winner = getWinner(arr, 7, k);
23 printf("Winner: %d\n", winner);
24 return 0;
25}The code starts by assuming the first element is the maximum. It then iterates through the rest of the elements. If the current max is greater than the current element, increase the win count; otherwise, update the current max and reset the win count. The loop runs until an element wins k consecutive times or until the end of the array, returning the max.
This variant uses a concept very similar to the simulation approach but adds a breaking condition for improved efficiency. It exploits the game's characteristics by noting if the current maximum wins continuously even before counting to k, it will naturally reach the conclusion. This allows early termination if the maximum element becomes apparent quickly.
Time Complexity: O(n), potentially terminating faster.
Space Complexity: O(1).
1
Enhancing Python code with strategic exit, it estimates remaining rounds against advantageous maximum, ceasing prematurely if ongoing dominance is logically assertable.