You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Last Surviving Number in Loop

Nicholas Wong
Nicholas Wong

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.