Coding the Josephus Problem

Nearest_Lower_Square.csv

solution1.js

// My ugly first solution draft
const solution = (n) => {
  // Ensure n is number
  if (typeof n !== 'number') return 0;
  // Ensure n is > 0
  if (n < 1) return 0;

  // This array represents the circle
  const arr = [];
  // Fill the array with 1 ones to begin
  // 1 - means alive
  // 0 - means elminated
  for (let i = 0; i < n; i++) arr[i] = 1;

  // Iterate until the sum of the array is 1,
  // which means 1 is the last man standing
  while (arr.reduce((a, b) => a + b, 0) !== 1) {
    // Find who is the next guy alive and standing to the left
    for (let i = 0; i < n; i++) {
      // Find a living soldier
      if (arr[i] === 1) {
        // Split the circle in two segments
        let after = arr.slice(i+1, arr.length);
        let before = arr.slice(0, i);
        // Find the next guy alive
        if (after.reduce((a, b) => a + b, 0) > 0) {
          let nextAliveIndex = i + 1 + after.findIndex((a) => a === 1);
          // Eliminate
          arr[nextAliveIndex] = 0;
        } else if (before.reduce((a, b) => a + b, 0) > 0) {
          let nextAliveIndex = before.findIndex((a) => a === 1);
          // Eliminate
          arr[nextAliveIndex] = 0;
        }
      }
    }
  }

  // As position in the diagram start from 1
  return 1 + arr.findIndex((a) => a === 1);
}

const position = solution(5);
console.log(position); // >>> 3

solution2.js

let nearestLowerPow2 = function (x) {
  if (x == 0) return 0;
  const arr = [1, 2, 4, 8, 16];
  arr.forEach(function(n) {
    x |= (x >> n);
  });

  return x - (x >> 1);
}

// Second solution based on the formula
const solution2 = (n) => {
  let lowPow2 = nearestLowerPow2(n);
  return 2*(n-lowPow2)+1;
};

const position = solution2(5);
console.log(position); // >>> 3

solution3.js

// Third solution binary based
const solution3 = (n) => {
  // Convert to BIN
  const binaryStr = Number(n).toString(2);
  // Swapping digits
  const newBinaryStr = (binaryStr + binaryStr[0]).replace(/./, '');
  // Convert back to DEC
  return parseInt(newBinaryStr, 2);
};

const position = solution3(5);
console.log(position); // >>> 3