Why isn't this algorithm for the Josephus problem working in c, when it works in python?

Question

So I needed to solve a version of the Josephus problem, in which we assume we have n robots standing in a circle, all of which are on in the beginning. We start to turn the robots off in rounds. Robot number 1 is turned off in the first round, then we count the robots that are on until we reach number k, and we turn that robot off. The process goes on until exactly one robot remains on.

So the problem is that we should write an algorithm that takes n and k as input and prints an array of the robots turned off each round in order. For example if n = 13 and k = 2, the answer would be 1, 3, 5, 7, 9, 11, 13, 4, 8, 12, 6, 2

I wrote a python code for the problem, with the intention to convert it to C afterwards Here's the python code, to show the general idea of the algorithm:

n = int(input())
first = list(range(1 , n + 1)) 

k = int(input())

result = [] # with n - 1 segments

def removal(i):
    while i < len(first) - 1:
        first[i] = first[i + 1]
        i += 1
    first.pop() # n -= 1

i = 0
while len(first) > 1: # n > 1
    result.append(first[i])
    removal(i)
    i += k-1
    i %= len(first)

print(result)

And here's the C version:

#include <stdio.h>

int main()
{
    int n , k;
    scanf("%d" , &n);
    scanf("%d" , &k);
    int len = n;
    int first[n + 1];
    
    int j = 0; //Taking array first as input
    while (j < n)
    {
        first[j] = j + 1;
        j++;
    }

    int result[n - 1];
    int i = 0;
    j = 0;

    while (n > 1)
    {
        result[j] = first[i]; 
        j++;

        while (i < n-1) //Removing the i th item of array first
        {
            first[i] = first[i + 1];
            i++;
        }
        n--;
        i += (k-1);
        i %= n;

    }
    
    j = 0;
    while (j < len-1)
    {
        printf("%d " , result[j]);
        j++;
    } 

    return 0;

}

For example, in the case I mentioned above, for n = 13 and k = 2, the C code prints: 1 3 4 5 6 7 8 9 10 11 12 13

As I said, the python code works, but the C version of it doesn't and I can't figure out why. Can anyone explain what I should do to fix the code in c?

Answer 1

The problem is that python uses pass by value (see What's the difference between passing by reference vs. passing by value?) and your C program does not copy the value of i while removing the i'th element, it rather modifies it. If you change part of your removal loop to:

int m = i;
while (m < n-1) //Removing the i th item of array first
{
    first[m] = first[m + 1];
    m++;
}

It should work like you expect. This is rather not a question for stackoverflow as you might have guessed from the comments you got.