Oct 10, 2024 · Oct 10, 2024 · Oct 10, 2024
diff --git a/Recursive/Josephus.js b/Recursive/Josephus.js
 /**
 * @function Josephus
 * @description recursive implementation of the Josephus function.
 * @param {Integer[]} collection - The integer array.
 * @param {Integer} - The step size.
 * @return {Integer} - The last integer in the list.
 * @see [JosephusProblem](https://en.wikipedia.org/wiki/Josephus_problem)
 * @example [1,2,3,4,5,6,7] with step 3 = 4
 */

 const josephus = (collection, step) => {
  // return null for invalid steps that are less than or equal to 0
  if (step <= 0 || collection.length === 0) {
    return null
  }
  if (collection.length === 1) {
    return collection[0]
  } else {
    step = (step - 1) % collection.length
    collection.splice(step, 1)
    return josephus(collection, step + collection.length)
  }
 }

 export { josephus }
diff --git a/Recursive/test/Josephus.test.js b/Recursive/test/Josephus.test.js
 import { josephus } from '../Josephus'

 describe('Josephus', () => {
  const collection = [1, 2, 3, 4, 5, 6, 7]
  const collection1 = [1]
  const collection2 = []

  it('should return 4 for step size of 3', () => {
    const step = 3
    expect(josephus([...collection], step)).toBe(4)
  })

  it('should return 4 for a step size of 10', () => {
    const step = 10
    expect(josephus([...collection], step)).toBe(4)
  })

  it('should return null for a step size of 0 as it is invalid', () => {
    const step = 0
    expect(josephus([...collection], step)).toBeNull()
  })

  it('should return 7 for a step size of 1000', () => {
    const step = 1000
    expect(josephus([...collection], step)).toBe(7)
  })

  it('should return null for a step size of -1 as it is invalid', () => {
    const step = -1
    expect(josephus([...collection], step)).toBeNull()
  })
  it('should return 1 for a collection with just 1', () => {
    const step = 2
    expect(josephus([...collection1], step)).toBe(1)
  })
  it('should return null for an empty collection as it is invalid', () => {
    const step = 3
    expect(josephus([...collection2], step)).toBeNull()
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,25 @@
		/**
		* @function Josephus
		* @description recursive implementation of the Josephus function.
		* @param {Integer[]} collection - The integer array.
		* @param {Integer} - The step size.
		* @return {Integer} - The last integer in the list.
		* @see [JosephusProblem](https://en.wikipedia.org/wiki/Josephus_problem)
		* @example [1,2,3,4,5,6,7] with step 3 = 4
		*/

		const josephus = (collection, step) => {
		// return null for invalid steps that are less than or equal to 0
		if (step <= 0 \|\| collection.length === 0) {
		return null
		}
		if (collection.length === 1) {
		return collection[0]
		} else {
		step = (step - 1) % collection.length
		collection.splice(step, 1)
Copy link Collaborator appgurueuOct 10, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. This is$O(n)$ so you get$O(n^2)$ runtime, which is very naive. Wikipedia shows formulae that achieve$O(n)$ or$O(k\log{n})$ runtime, both of which are substantially better. And even besides those, I can pretty easily come up with$O(n \log{n})$ algorithms based on decremental data structures which support this "splice" operation in logarithmic time (such as an initially balanced k-nary tree augmented with counts). This algorithm also doesn't really benefit from recursion. It would be clearer as a simple`while` loop: while(collection.length>1){/* kill someone */}returncollection[0]
		return josephus(collection, step + collection.length)
		}
		}

		export { josephus }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,40 @@
		import { josephus } from '../Josephus'

		describe('Josephus', () => {
		const collection = [1, 2, 3, 4, 5, 6, 7]
		const collection1 = [1]
		const collection2 = []

		it('should return 4 for step size of 3', () => {
Copy link Collaborator appgurueuOct 10, 2024 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. Repetitive tests of the form "should return X for Y" should use`it.each`
		const step = 3
		expect(josephus([...collection], step)).toBe(4)
		})

		it('should return 4 for a step size of 10', () => {
		const step = 10
		expect(josephus([...collection], step)).toBe(4)
		})

		it('should return null for a step size of 0 as it is invalid', () => {
		const step = 0
		expect(josephus([...collection], step)).toBeNull()
		})

		it('should return 7 for a step size of 1000', () => {
		const step = 1000
		expect(josephus([...collection], step)).toBe(7)
		})

		it('should return null for a step size of -1 as it is invalid', () => {
		const step = -1
		expect(josephus([...collection], step)).toBeNull()
		})
		it('should return 1 for a collection with just 1', () => {
		const step = 2
		expect(josephus([...collection1], step)).toBe(1)
		})
		it('should return null for an empty collection as it is invalid', () => {
		const step = 3
		expect(josephus([...collection2], step)).toBeNull()
		})
		})