Interview Practice 18 - Last Surviving Number in Loop


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.


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.


last in list def last_remain_number_in_list(list, m): length = len(list) while len(list) > 1: index = m % len(list) list.pop(index) return list.pop() # main, answer is 5 list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] print last_remain_number_in_list(list, 8)

include <stdio.h> int main() { int i,k,m,n,num[50],*p; printf("input number of person:n="); scanf("%d",&n); printf("input number of the quit:m="); //留下->18题 scanf("%d",&m); //留下->18题 p=num; for(i=0;i<n;i++) (p+i)=i+1; //给每个人编号 i=0; //报数 k=0; //此处为3 // m=0; //m为退出人数 //去掉->18题 while(m<n-1) { if((p+i)!=0) k++; if(k3) { *(p+i)=0; //退出,对应的数组元素置为0 k=0; m++; } i++; if(in) i=0; } while(*p==0) p++; printf("The last one is NO.%d/n",*p); }

int LastRemaining_Solution2(int n, unsigned int m) { // invalid input if(n <= 0 || m < 0) return -1; // if there are only one integer in the circle initially, // of course the last remaining one is 0 int lastinteger = 0; // find the last remaining one in the circle with n integers for (int i = 2; i <= n; i ++) lastinteger = (lastinteger + m) % i; return lastinteger; }

Show Comments