You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# Last Surviving Number in Loop

## Consider

Consider there is a list containing N numbers, and which formed a ring. That is, item n+1 is item 1.

Construct an algorithm such that it traverses through the ring, and remove the Mth item. Repeat this process until there is only one number left in the ring and then output this number.

For example, in the list {10, 11, 12}, and the remove the 3th item in every loop. Then in the first loop, 12 will be removed, followed by 10. Therefore the last surviving number is 11.

## Solution

In python, it’s easy because it has build-in function to resize an array. We can construct an array, then pop the Kth item in every loop, where K = M mod Length of List.

## Example

``````def last_remain_number_in_list(list, m):
while len(list) > 1:
index = m % len(list)
list.pop(index)
return list.pop()

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print last_remain_number_in_list(list, 8) # answer is 5
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.