Last Remaining Number in a Circle

1. Problem Description

Every Children’s Day, NowCoder prepares small gifts for children in an orphanage, and this year is no exception. HF, as a veteran member of NowCoder, also prepares some games. In one game, the children first stand in a large circle. Then he chooses a number m and asks the child numbered 0 to start counting. Each child who calls out m-1 leaves the circle to sing a song, may choose a gift, and does not return. Counting 0…m-1 continues from the next child until only one child remains. That child does not need to perform and receives the special prize. Determine which child gets the gift. (The children are numbered from 0 to n-1.)

If there are no children, return -1.

2. Approach

• Simulation
• Recursion
• Iteration

3. Implementation

3.1. Simulation

// Space: O(N)
// Time: O(N²)
func LastRemaining_Solution(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}
	queue := make([]int, 0)
	for i := 0; i < n; i++ {
		queue = append(queue, i)
	}

	index := 0
	for len(queue) != 1 {
	    // This is similar to index operations in a circular queue
		index = (index + m - 1) % len(queue)
		queue = remove(queue, index)
	}
	return queue[0]
}

func remove(a []int, i int) []int {
	newData := make([]int, 0)
	newData = append(newData, a[:i]...)
	newData = append(newData, a[i+1:]...)

	return newData
}

3.2. Recursion

// Space: O(N)
// Time: O(N)
func LastRemaining_Solution2(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}

	return f(n, m)
}

func f(n int, m int) int {
	if n == 1 {
		return 0
	}
	x := f(n-1, m)
	return (x + m) % n
}

3.3. Iteration

// Time complexity: O(N)
// Space complexity: O(1)
func LastRemaining_Solution3(n int, m int) int {
	if n <= 0 || m <= 0 {
		return -1
	}

	index := 0
	for i := 2; i <= n; i++ {
		index = (index + m) % i
	}
	return index
}

4. References

• Children’s Game (Last Number Remaining in a Circle) - NowCoder