A New Algorithm for the Josephus Problem Using Binary Count Tree

DOI

10.2991/cecs-18.2018.26How to use a DOI?

Keywords

Josephus problem, BST, Binary count tree, Binary recursion.

Abstract

This paper presents a new efficient algorithm for the Josephus problem using Binary Count Tree. Binary count tree is a data structure ameliorated from the BST which additionally records the node-count of each sub tree. In this algorithm, the whole Joseph circle is put into the binary count tree. The target node can be quickly found by moving the pointer between the child node and the parent node, and then the target will be deleted and the related node-counts will be updated. Analysis and experiments shows that this algorithm can find out an entire Joseph sequence in time O(n*log n).

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Jian Li
AU  - Yanzhou Ma
AU  - Zesheng Gao
AU  - Xinyu Hu
PY  - 2018/07
DA  - 2018/07
TI  - A New Algorithm for the Josephus Problem Using Binary Count Tree
BT  - Proceedings of the 2018 International Symposium on Communication Engineering & Computer Science (CECS 2018)
PB  - Atlantis Press
SP  - 135
EP  - 140
SN  - 2352-538X
UR  - https://doi.org/10.2991/cecs-18.2018.26
DO  - 10.2991/cecs-18.2018.26
ID  - Li2018/07
ER  -