This is a josephus problem, using a circular linked list takes cuadratic time O( m n ), I think the josephus problem can be solved using rank trees in O(n log n).
Construct a rank tree from an array with n elements storing the elements in a binary tree in in-order sequence ( Constructor ). Store in each node T the size of the subtree whose root is T. We have the following operation for the tree: 1.find(int k) returns the item at rank (index) k. 2.remove(int k) removes the item at rank k. 3.size() returns the current size ( size is the number of elements in the subtree of a node S) Find and Remove takes O( log n ) and Constructor takes O( n ). 2011/2/9 Rel Guzman Apaza <[email protected]> > maybe using a circular linked list. > > 2011/2/9 punnu <[email protected]> > > Suppose n people are arranged in a circle. Number the people from 1 to >> n. in the clockwise order. We are given an integer ,m <= n. Beginning >> with the person with designated number 1, we proceed around the circle >> (in clockwise order) removing every mth person. After each person is >> removed, counting continues around the circle that >> remains. This process continues until all the n people have been >> removed. . The .m-permutation is defined as the order in which the >> people have been removed. As an example, if n = 7, m = 3, then the 3 - >> permutation is 3,6,2,7,5,1,4. >> Give an O(n log n) time algorithm which given m and n outputs the m- >> permutation. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
