3
\$\begingroup\$

I have solved a spoj question CLASS LEADER. 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.

#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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Check this out. \$\endgroup\$ – vnp Dec 15 '17 at 19:26
  • 1
    \$\begingroup\$ Are you required to use a linked list? It seems like a vector of integers would be a far better choice. \$\endgroup\$ – Austin Hastings Dec 15 '17 at 22:40
6
\$\begingroup\$

Don't use using namespace std


Prefer '\n' to std::endl

The reason is that std::endl flushes the stream. This can lead to performance issues when called frequently (Not your primary performance issue but still just good practice.) Furthermore many people consider good code to be explicit and would prefer a call to std::flush when you want to flush the stream.


Avoid Globals

OOP provides encapsulation so that variables that should not be accessible from outside a given scope can't be. Not only is it harder for you to make mistakes altering variables on a large scale but it also makes anyone touching your code unable to do it too.


Memory Leaks

You have many calls to new but do not have a single call to delete. Your program leaks every bit of memory it allocates. The two main problem areas are both here:

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);
}

first you create a new node pointed to by q and then immediately assign q to p therefor making it impossible to ever delete the memory you just allocated.

Then you assign q->next = p->next; effectively unlinking p from the rest of the list. Once the function goes out of scope p is lost and the memory pointed to by it can never be freed.


Prefer nullptr to NULL

NULL is a C Macro that is may or may not defined as 0 and can cause ambiguity. nullptr on the otherhand is a keyword.

while (r->next != NULL)

And don't compare values to NULL (or nullptr) - pointers convert implicitly to Booleans. Prefer instead to represent the conditional as:

while (r->next)

Prefer initialization over assignment

struct node {
    int data;
    node* next;
};

Your node is not really complete. Imagine I do this:

node myNode;
std::cout << myNode.data;

What will print? We don't know. It's undefined behavior.

Even if you provided a default constructor (which is overkill and unnecessary) and assigned the variables default values there it would be suboptimal because you will essentially giving your variables garbage values only to give them the meaningful ones momentarily later.

struct node {
    int data{ 0 };
    node* next{ nullptr };
}

Here the node is constructed properly and without the potential for UB. If you don't want to assign data the default value of 0 you could create a constructor that takes an int as a parameter and initializes data to the value passed. Something like:

struct node {
    int data;
    node* next{ nullptr };
    node(int data) : data{ data } {};
}

Naming

Use better names. You will thank yourself months from now when rereading old code. Single letter variables are hard to keep track of and require you to memorize your code when more explicit naming makes that unnecessary. The exception to that are the parameters of the problem you are being given to solve. Well named functions also better help understand what is being done as well.

Take for instance your createLL function. This function doesn't create a linked list. It adds a single node to the end of the list. add_node or push_back would be more appropriate names.

And func() is the most generic possible name for a function you can come up with. I don't expect to see that name outside of pseudocode.


Prefer prefix over postfix

Your code is the perfect example of when to use both of these. In your for loop you use postfix which tells me you are incrementing with postfix as a matter of course which is a bad habit to get into. Postfix creates a copy, then increments the original and then returns the copy. This can be useful such as in you while loops. If you used prefix there you would end up with an off-by-one error. The constant copying that is done in your while loops is trivial with integral values like you use but if it was a non-trivial (perhaps a user defined class) value a simple solution would be to decrement your variable with prefix within the loop itself.


Omit return 0

The compiler will return from the end of main() without you needed to tell it to. Not only is it unnecessary but by doing so you signal to readers of your code that you may return error codes elsewhere in the program (which you don't).


int t;
cin >> t;

This is an input that you didn't provide in your description of the problem. You dealt with it correctly programmatically but it is an important requirement and thus should have been in your description. It is important to note that this is considered a reasonable exception to initializing variables. You define your variable and immediately assign it via input from the user.

int n, m, o;

Don't declare more than one variable per line. It can be misleading (with pointer assignment and initialization in particular) and can make it hard to track.


for (int i = 1; i<n; i++) {         //created linked list with values index+1
    createLL(i + 1);
}

If you start i at 2 the you don't need to add 1 when passing it as a parameter. Note the change from < to <= in the comparison.

for (int i = 2; i <= n; ++i) {
    createLL(i);
}

while (r->next != NULL) {           //traverse to the end
    r = r->next;
}
r->next = head;                     //created a circular linked list

This whole loop is unnecessary. You already know where the last element in your list is.

tail->next = head;

Put all of that together and it looks something like this:

#include <iostream>

struct node {
    int data{ 0 };
    node* next{ nullptr };
};

void add_node(node*& tail, int n) {
    node* temp = new node();
    temp->data = n;
    tail->next = temp;
    tail = temp;
}

int josephus(node*& start_node, int index_shift) {
    if (start_node->next == start_node) {
        return start_node->data;
    }

    int shift_count = index_shift;
    node* temp = start_node;

    while (shift_count--) {
        start_node = temp;
        temp = temp->next;
    }

    start_node->next = temp->next;
    delete temp;
    return josephus(start_node, index_shift);
}

int main() {
    int num_tests; // formerly T
    std::cin >> num_tests;

    node* head = new node();


    while (num_tests--) {
        int num_nodes; // formerly n
        int start_index; //formerly m
        int shift_by; //formerly o
        std::cin >> num_nodes >> start_index >> shift_by;

        if (num_nodes == 1) {
            std::cout << num_nodes << '\n';
            continue;
        }

        head->data = 1;
        node* tail = head;

        for (int i = 2; i <= num_nodes; ++i) {
            add_node(tail, i);
        }

        tail->next = head;

        while (head->data != start_index) {
            head = head->next;
        }

        std::cout << josephus(head, shift_by) << '\n';
    }
    delete head; // just noticed I never deleted this. (Sure the program
    // ends here but you always want to clean up your memory.)
}

Note the pointers passed as reference so that I didn't need a global variable. More explicit names like start_node, num_students, josephus, and temp. I'm not implying my names are the best but they are clearer and more explicit like add_node. Note the calls to delete when necessary.


But this isn't really the best solution for several reasons:

  • Avoid naked new/delete.

    You could use smart pointers but they can be a bit unwieldy when being repointed frequently. You should use them anyway when you can but we are going to change our solution.

  • The data structure is poorly made.

    I understand that C++ doesn't have a circular list and that a circular list seemed especially appealing for this problem but a.) implementing a full scale data structure is a much more complicated task than this b.) there are simpler workarounds. Your circular list is just a bunch of exposed nodes that you manually link together at the end. A good data structure design would not expose the nodes directly and would use templates to provide for reusability.

  • You should prefer standard data structures.

    Years of man hours have gone into them. If you want to remake some for a learning exercise: Great! But it doesn't belong with your Josephus solution.

  • We are still getting TLE.


The way to use a standard std::list as a circular list would be with the use of iterators. I have the following example:

#include <iostream>
#include <iterator>
#include <list>

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        std::list<int> students;

        for (auto i = 1; i <= num_students; ++i)
        {
            students.push_back(i);
        }

        std::list<int>::iterator it = students.begin();
        for (auto i = 1; i < start_index; ++i)
        {
            ++it;
            if (it == students.end())
            {
                it = students.begin();
            }
        }

        auto countdown = num_students - 1;
        while (countdown--)
        {
            for (auto i = 0; i < steps; ++i)
            {
                ++it;
                if (it == students.end())
                {
                    it = students.begin();
                }
            }

            if (it != students.begin())
            {
                it = students.erase(it);
                --it;
            }
            else
            {
                students.erase(it);
                it = students.end();
                --it;
            }
        }

        std::cout << *it << '\n';
    }
}

In this example you simply use an iterator to traverse the list much like you did with your nodes. However here we have a standard memory-safe container. no leaks. No manual memory management. You have to take some care to ensure you are incrementing and wrapping correctly and that you never dereference your std::list::end() but this is much safer. (And when you break things it will shout at you and you can get to debugging faster.) You may notice that I did not implement this with recursion. Feel free to reimplement it that way as a learning experience.

(Also be aware that both of these solutions really should factor out the entire problem into one higher level function. Encapsulation is important in C++ and a decluttered main() is highly desirable.)


This still isn't the best solution. Mostly because at the end of the day programming challenges like this are not generally going to be successfully completed by brute force. This solution still gets TLE.

as @vnp noted this is the Josephus Problem. As such it can actually be expressed mathematically. The following expression was found on Geeks for Geeks:

#include <iostream>

int josephus(int num_students, int steps)
{
    if (num_students == 1)
    {
        return 1;
    }
    else
    {
        /* The position returned by josephus(n - 1, k) is adjusted because the
        recursive call josephus(n - 1, k) considers the original position
        k % n + 1 as position 1 */
        return (josephus(num_students - 1, steps) + steps - 1) % num_students + 1;
    }
}

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        auto answer = josephus(num_students, steps);

        answer = (answer + start_index) % num_students;

        if (answer != 0) {
            std::cout << answer << '\n';
        }
        else
        {
            std::cout << num_students << '\n';
        }
    }
}

The solution works as the size decreases recursively and k % n + 1 tracks the position and allows for skipping over otherwise removed candidates. Then the start_index is applied to shift the survivor respectively.


Now is the point I get to disappoint everyone! This still returns TLE. I suspect the excessive calls to % which are expensive to process for the performance issue. I have tried viewing the more complicated mathematical expression of the solution but it is over my head. It is available in the Wikipedia page I linked. I hate to be anti-climactic so if anyone else has the solution I encourage you to post it in an answer so I can upvote it.

\$\endgroup\$
  • 1
    \$\begingroup\$ NULL is a macro defined to be a null pointer constant. Both 0 and nullptr qualify. \$\endgroup\$ – Deduplicator Jul 18 '18 at 0:23
  • 1
    \$\begingroup\$ The point I'm making is that it can be 0, but it can also be a different null pointer constant, and you cannot know which. It's a QOI-issue, and the latitude to implementers means extra care is needed using it (only using it in a pointer-context is supported), thus best avoid it completely. \$\endgroup\$ – Deduplicator Jul 18 '18 at 1:52
2
\$\begingroup\$

I suspect the "new"-calls to take up most of the time. Pre-allocate a bunch of nodes and pop them from the allocated container:

node* pool;    
int pcount = 100; // or whatever is max
int main() {
pool = new node[pcount];
...
// node* t = new node();
node* t = &pool[--pcount];

(error handling left as exercise)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy