Algorithm

Last Surviving Number in Loop

Nicholas Wong

Nicholas Wong

— 1 min read
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

Read more