Sponsored
Sponsored
We utilize two separate queues to maintain indices of Radiant and Dire senators. In each round, senators from both parties execute their rights and effect bans on their opponent. The process continues until one queue becomes empty, indicating that all senators from one party have been eliminated.
Time Complexity: O(n), where n is the length of the senate, since each senator is processed a finite number of times.
Space Complexity: O(n), for storing indices in queues.
1#include <stdio.h>
2#define MAX_SIZE 10000
3#define QUEUE_EMPTY -1
4
5typedef struct Queue {
6 int items[MAX_SIZE];
7 int front, rear;
8} Queue;
9
10void initQueue(Queue* q) {
11 q->front = 0;
12 q->rear = -1;
13}
14
15int isEmpty(Queue* q) {
16 return q->rear < q->front;
17}
18
19void enqueue(Queue* q, int value) {
20 if (q->rear < MAX_SIZE - 1) {
21 q->items[++q->rear] = value;
22 }
23}
24
25int dequeue(Queue* q) {
26 if (!isEmpty(q)) {
27 return q->items[q->front++];
28 }
29 return QUEUE_EMPTY;
30}
31
32const char* predictPartyVictory(char* senate) {
33 Queue radiantQueue, direQueue;
34 initQueue(&radiantQueue);
35 initQueue(&direQueue);
36 for (int i = 0; senate[i] != '\0'; i++) {
37 if (senate[i] == 'R') enqueue(&radiantQueue, i);
38 else enqueue(&direQueue, i);
39 }
40
41 int len = strlen(senate);
42 while (!isEmpty(&radiantQueue) && !isEmpty(&direQueue)) {
43 int rIdx = dequeue(&radiantQueue);
44 int dIdx = dequeue(&direQueue);
45 if (rIdx < dIdx) enqueue(&radiantQueue, rIdx + len);
46 else enqueue(&direQueue, dIdx + len);
47 }
48 return isEmpty(&radiantQueue) ? "Dire" : "Radiant";
49}
50In the solution, we employ a queue to separately track Radiant and Dire senators' indices. For each senate round, we compare indices of both parties. The senator with a smaller index, indicating an earlier position, bans the other and gets scheduled for the next round with an increased index (index + senate length). The queue that first becomes empty indicates the losing party.