text: /*******************************************************************
  Copyright(c) 2016, Harry He
  All rights reserved.
  
  Distributed under the BSD license.
  (See accompanying file LICENSE.txt at
  https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
  *******************************************************************/
  
  //==================================================================
  // 《剑指Offer——名企面试官精讲典型编程题》代码
  // 作者：何海涛
  //==================================================================
  
  // 面试题62：圆圈中最后剩下的数字
  // 题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里
  // 删除第m个数字。求出这个圆圈里剩下的最后一个数字。
  
  #include <cstdio>
  #include <list>
  
  using namespace std;
  
  // ====================方法1====================
  int LastRemaining_Solution1(unsigned int n, unsigned int m)
  {
      if(n < 1 || m < 1)
          return -1;
  
      unsigned int i = 0;
  
      list<int> numbers;
      for(i = 0; i < n; ++ i)
          numbers.push_back(i);
  
      list<int>::iterator current = numbers.begin();
      while(numbers.size() > 1)
      {
          for(int i = 1; i < m; ++ i)
          {
              current ++;
              if(current == numbers.end())
                  current = numbers.begin();
          }
  
          list<int>::iterator next = ++ current;
          if(next == numbers.end())
              next = numbers.begin();
  
          -- current;
          numbers.erase(current);
          current = next;
      }
  
      return *(current);
  }
  
  // ====================方法2====================
  int LastRemaining_Solution2(unsigned int n, unsigned int m)
  {
      if(n < 1 || m < 1)
          return -1;
  
      int last = 0;
      for (int i = 2; i <= n; i ++) 
          last = (last + m) % i;
  
      return last;
  }
  
  // ====================测试代码====================
  void test(const char* testName, unsigned int n, unsigned int m, int expected)
  {
      if(testName != nullptr)
          printf("%s begins: \n", testName);
  
      if(LastRemaining_Solution1(n, m) == expected)
          printf("Solution1 passed.\n");
      else
          printf("Solution1 failed.\n");
  
      if(LastRemaining_Solution2(n, m) == expected)
          printf("Solution2 passed.\n");
      else
          printf("Solution2 failed.\n");
  
      printf("\n");
  }
  
  void test1()
  {
      test((char *)"test1", 5, 3, 3);
  }
  
  void test2()
  {
      test((char *)"test2", 5, 2, 2);
  }
  
  void test3()
  {
      test((char *)"test3", 6, 7, 4);
  }
  
  void test4()
  {
      test((char *)"Test4", 6, 6, 3);
  }
  
  void test5()
  {
      test((char *)"Test5", 0, 0, -1);
  }
  
  void test6()
  {
      test((char *)"Test6", 4000, 997, 1027);
  }
  
  int main(int argc, char* argv[])
  {
      test1();
      test2();
      test3();
      test4();
      test5();
      test6();
  
      return 0;
  }
  
  