Josephus Recurrence

Famous Josephus's problem solution.

Recursive solution:

int josephus(int n, int m)   
{   
 if (n == 1)  
      return 0;   
 return (josephus (n-1, m) + m) % n;   
}

Iterative solution:

ans=0;
for(i=2;i<=n;i++)
{
 ans=(ans+m)%i;
}

when m=2, then the following will be useful. Found it here.

int f(int n) 
{
    if(n == 1) return 1;
    return (f((n-(n&1))>>1)<<1) + ((n&1)?1:-1);
}