Josephus problem


  • 0
    P

    https://en.wikipedia.org/wiki/Josephus_problem

    Sorry, I obviously have made my question unlike Josephus here while I did not mean it. So I correct it below.

    You have a circle of n apples, and you first eat 0 apple(no apple), and you skip k - 1 apples and eat the kth apple, so on so forth until there is only one apple. If the apple does not want to be eaten, which position should it be at the beginning.

    Eg, if there is one apple, the apple just needs to be at position 1. If there are 10 apples, the apple needs to be at position 5 if k = 2.

    def josephus(n, k):
    	if n == 1:
    		return 1
    	return (josephus(n - 1, k) + k - 1) % n + 1
    
    def josephus2(n):
    	power = 1
    	while power * 2 <= n:
    		power *= 2
    	return (n - power) * 2 + 1
    

  • 0
    N
    This post is deleted!

  • 0
    N
    This post is deleted!

  • 0
    C

    @pushazhiniao I think this is inaccurate. "If there are 10 apples, the apple needs to be at position 5 if k = 2." This seems to be a solution to the original Josephus problem. But not for the apple problem here. My own simulation says 4 is the position of apple.


  • 0
    P

    @cau-seoi-dyun-dou Hi, I am using the result from wikipedia. I did not get the right result at first, but when I really understand the question, the result is correct. If you did not get the right result, try again.


  • 0
    C

    @pushazhiniao In your problem (say A), the first apple eaten is the first. In the Josephus problem (say B), the first person killed is the k-th. To illustrate the difference. Let k=2. n=5.
    In the first round of A, apples in position {1,3,5} are eaten.
    In the first round of B, people in position {2,4} are killed.


  • 0
    P

    @cau-seoi-dyun-dou Okay. I just saw that the contest has used a similar one. But it starts killing at 1 while Josephus starts killing at k.

    For example, 123456789
    You always start counting from last killed. At beginning, you assume that 0 is last killed one.
    Counting starts from 0: You kill 2 first.
    So you get: 13579
    Then you get: 37
    Finally you get: 3

    This is how you can use the code above. Otherwise, well.


  • 0
    P

    @pushazhiniao
    I always prefer loop to recursive calling.

    if(n <= 0)
    return 0;
    if(k < 1 )
    return 0;

    	int left = n;
    	boolean[] visited = new boolean[n + 1];
    	int p = 1;
    	int step = 1;
    	while(left > 1) {
    		while(step < k) {
    			p++;
    			if(p > n)
    				p = 1;
    			if(visited[p] == true);
    			else {
    				step++;
    			}
    		}
    		// mark the apple being eaten
    		visited[p] = true;
    		step = 0;	
    		left--;
    	}
    	for(int i = 1; i <=n; i++)
    		if(visited[i] == false)
    			return i;
    	return -1;

  • 0
    C

    @pushazhiniao Well, you can rotate backward by k, then you'll get the original josephus problem. So f(n,k) = ( josephus(n,k) - k ) % n + 1.


  • 0
    P

    @cau-seoi-dyun-dou Theoretically, you can use the output of Josephus as an index. If you do, rotate by k - 1 and the function should still be f(n,k) = ( josephus(n,k) + k - 1) % n + 1 because Josephus assumes the last killed at the beginning is 0. Then you map the id to the rotated array.


  • 0
    P

    Just for the 390 which is only similar to this problem.

    class Solution(object):
        def lastRemaining(self, n):
            """
            :type n: int
            :rtype: int
            """
            left, right = 1, n
            power, reverse = 2, False
            while left < right:
                if not reverse:
                    leftPrev = left
                    left += power / 2
                    if left < right and (right - leftPrev) % power == 0:
                        right -= power / 2
                    reverse = True
                else:
                    rightPrev = right
                    right -= power / 2
                    if left < right and (rightPrev - left) % power == 0:
                        left += power / 2
                    reverse = False
                power *= 2
            return left
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.