search for modified josephus problem. you will get the answer :)
On Wed, Feb 9, 2011 at 4:52 PM, punnu wrote:
> 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
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 i
maybe using a circular linked list.
2011/2/9 punnu
> 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) remo
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