I have solved a spoj question CLASS LEADER , i don’t know if i can explain the question well but here it is, for each test case there are n students and a paper will be given to student m and now the game starts, the student m will pass the paper by o positions and the person who gets the paper gets eliminated and the game will be continued until one student is left
I actually solved the problem by first creating a linked list of size n using struct and then pointed last node to the front which made my list circular then i went to position m and then started the calling recursive call to function which moved by o positions and removed that node. I am unable to improve my code’s performance and getting TLE here’s my code
#include<iostream> using namespace std; struct node { int data; node* next; }; node* tail = new node(); //Global node void createLL(int n) { //adding node at end node* t = new node(); t->data = n; t->next = NULL; tail->next = t; tail = t; } int func(node* p, int k) { if (p->next == p)return p->data; int f = k; node* q = new node(); while (f--) { q = p; p = p->next; } q->next = p->next; func(q, k); } int main() { int t; cin >> t; while (t--) { int n, m, o; cin >> n >> m >> o; if (n == 1) { cout << n << endl; continue; } node* head = new node(); head->data = 1; head->next = NULL; tail = head; for (int i = 1; i<n; i++) { //created linked list with values index+1 createLL(i + 1); } node* r = head; while (r->next != NULL) { //traverse to the end r = r->next; } r->next = head; //created a circular linked list m--; while (m--) { head = head->next; //going to m'th position } int ans = func(head, o); //iterative call cout << ans << endl; } return 0; }