1

Here is one solution to the Josephus problem (where people are arranged in a circle and every other person is killed until only one remains):

import java.util.ArrayList;

public class test {

public static void main(String[] args) {

    ArrayList<Integer> chairArr = new ArrayList<Integer>();


    for (int i = 1; i <= 10; i++) {
        chairArr.add(i);
    }

    int result = 0;

    for (int i = 1; i < chairArr.size() - 1; i = i + 2) {
        chairArr.add(chairArr.get(i));
        result = i;
    }


    System.out.print("Result: " + chairArr.get(result));
    }
}

But what if, instead of skipping every other person, we increased the number skipped as we went through? That is, if 10 people were arranged in the circle, persons 1, 3, 6, 10, etc. were killed in that order. I think the modification would come in the i = i + 2 in the for loop, but I'm not sure.

I worked it out on paper, and this is the order of elimination, where asterisks denote the number to be removed:

0    *1*  2  3  4  5  6  7  8  9  10 
1     2  *3* 4  5  6  7  8  9  10
2     2   4  5 *6* 7  8  9  10
3     2   4  5  7  8  9 *10*
4     2   4  5  7 *8* 9
5     2   4  5  7 *9*
6     2   4 *5* 7
7    *2*  4  7
8    *4*  7
9     7 <-- Result

Thoughts?

Edit: Tried this modification of the for loop:

for (int j = 2; j < chairArr.size() - 1; j++) {
    for (int i = 1; i < chairArr.size() - 1; i = i + j) {
        chairArr.add(chairArr.get(i));
        result = i;
    }
}

This won't work because after the initial pass where j = 2, the inner loop will already have narrowed the list down to one candidate so the outer loop never completes.

Community
  • 1
  • 1
Comrade_Question
  • 305
  • 1
  • 2
  • 10
  • I was about to update the post to say that no, that is not the correct place to make it happen. If you do something like `i = i + j` where j is incrementing, it processes the inner loop skipping every other person, then does it again skipping every three people, etc. Except we've already narrowed it down to one person after the first value of j, so it never escapes the outer loop. – Comrade_Question Jul 06 '14 at 15:19

0 Answers0