234 ms·
https://en.wikipedia.org/wiki/Josephus_problem https://en.wikipedia.org/wiki/Josephus_problem Mistook the name. Yep, just shift the binary representation of t
by baybal2 7y ago
https://en.wikipedia.org/wiki/Josephus_problem https://en.wikipedia.org/wiki/Josephus_problem
Mistook the name.
Yep, just shift the binary representation of the total number of members by 1 bit
/**
*
* @param n (41) the number of people standing in the circle
* @return the safe position who will survive the execution
* ~Integer.highestOneBit(n*2)
* Multiply n by 2, get the first set bit and take its complement
* ((n<<1) | 1)
* Left Shift n and flipping the last bit
* ~Integer.highestOneBit(n*2) & ((n<<1) | 1)
* Bitwise And to copy bits exists in both operands.
*/
public int getSafePosition(int n) {
return ~Integer.highestOneBit(n*2) & ((n<<1) | 1);
}