/
096_LastNumberInCircle.cpp
114 lines (90 loc) · 1.99 KB
/
096_LastNumberInCircle.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// Coding Interviews: Questions, Analysis & Solutions
// Harry He
#include <stdio.h>
#include <list>
using namespace std;
// ==================== Solution 1====================
int LastRemaining_Solution1(unsigned int n, unsigned int m)
{
if(n < 1 || m < 1)
return -1;
list<int> numbers;
for(unsigned int 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);
}
// ==================== Solution 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;
}
// ==================== Test Code ====================
void Test(char* testName, unsigned int n, unsigned int m, int expected)
{
if(testName != NULL)
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("Test1", 5, 3, 3);
}
void Test2()
{
Test("Test2", 5, 2, 2);
}
void Test3()
{
Test("Test3", 6, 7, 4);
}
void Test4()
{
Test("Test4", 6, 6, 3);
}
void Test5()
{
Test("Test5", 0, 0, -1);
}
void Test6()
{
Test("Test6", 4000, 997, 1027);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
return 0;
}