Problem Statement
Consider the set of integers between 1 and n, inclusive, and two positive integers c and k. You want to build an ordered list of k pairs (x1, y1), (x2, y2), ... (xk, yk) such that the following conditions are met.
- 1 ≤ xi < yi ≤ n for all i between 1 and k, inclusive.
- yi < xi+1 for all i between 1 and k-1, inclusive.
- (xi+1 + yi+1) - (xi + yi) = c for all i between 1 and k-1, inclusive.
For instance, consider n=5, c=4, and k=2. There are two stable lists of pairs: one is [(1, 2), (3, 4)] and the other is [(2, 3), (4, 5)]. The latter is the only maximal stable list of pairs in this example as its sum is (2+3+4+5) = 14.
Given n, c, and k, find one maximal stable list of pairs,
and return a
If there are many maximal stable lists of pairs, you may return any one of them.
If no stable list of pairs with the desired properties exists, you must return an empty
Definition
- Class:
- StablePairsDiv1
- Method:
- findMaxStablePairs
- Parameters:
- int, int, int
- Returns:
- int[]
- Method signature:
- int[] findMaxStablePairs(int n, int c, int k)
- (be sure your method is public)
Constraints
- n will be between 1 and 100, inclusive.
- c will be between 1 and 100, inclusive.
- k will be between 1 and 100, inclusive.
Examples
5
4
2
Returns: {2, 3, 4, 5 }
This example was described in the problem statement.
4
4
2
Returns: {1, 2, 3, 4 }
1
100
1
Returns: { }
When n=1, regardless of c and k, there is no way to build a pair.
3
100
1
Returns: {2, 3 }
With k=1 we are looking for stable lists that only contain a single pair of numbers. There are three stable lists: [(1, 2)], [(1, 3)], and [(2, 3)]. Obviously, the last one is the only maximal one in this case.
10
6
3
Returns: {2, 5, 6, 7, 9, 10 }
12
7
3
Returns: {4, 5, 6, 10, 11, 12 }
76
78
49
Returns: { }
61
94
10
Returns: { }
70
23
17
Returns: { }
43
30
47
Returns: { }
60
86
22
Returns: { }
87
18
7
Returns: {32, 33, 41, 42, 50, 51, 59, 60, 68, 69, 77, 78, 86, 87 }
77
22
17
Returns: { }
67
15
6
Returns: {28, 30, 36, 37, 43, 45, 51, 52, 58, 60, 66, 67 }
83
8
21
Returns: {2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, 42, 43, 46, 47, 50, 51, 54, 55, 58, 59, 62, 63, 66, 67, 70, 71, 74, 75, 78, 79, 82, 83 }
95
6
22
Returns: {31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95 }
100
48
3
Returns: {51, 52, 75, 76, 99, 100 }
63
10
9
Returns: {22, 23, 27, 28, 32, 33, 37, 38, 42, 43, 47, 48, 52, 53, 57, 58, 62, 63 }
92
4
26
Returns: {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 }
81
12
12
Returns: {14, 15, 20, 21, 26, 27, 32, 33, 38, 39, 44, 45, 50, 51, 56, 57, 62, 63, 68, 69, 74, 75, 80, 81 }
36
7
2
Returns: {31, 33, 35, 36 }
63
4
4
Returns: {56, 57, 58, 59, 60, 61, 62, 63 }
46
4
5
Returns: {37, 38, 39, 40, 41, 42, 43, 44, 45, 46 }
57
43
2
Returns: {34, 36, 56, 57 }
66
4
20
Returns: {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 }
73
5
15
Returns: {37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 71, 72, 73 }
75
7
16
Returns: {21, 23, 25, 26, 28, 30, 32, 33, 35, 37, 39, 40, 42, 44, 46, 47, 49, 51, 53, 54, 56, 58, 60, 61, 63, 65, 67, 68, 70, 72, 74, 75 }
56
4
2
Returns: {53, 54, 55, 56 }
64
48
3
Returns: {15, 16, 39, 40, 63, 64 }
88
9
16
Returns: {19, 21, 24, 25, 28, 30, 33, 34, 37, 39, 42, 43, 46, 48, 51, 52, 55, 57, 60, 61, 64, 66, 69, 70, 73, 75, 78, 79, 82, 84, 87, 88 }
50
30
3
Returns: {19, 20, 34, 35, 49, 50 }
66
12
8
Returns: {23, 24, 29, 30, 35, 36, 41, 42, 47, 48, 53, 54, 59, 60, 65, 66 }
85
21
8
Returns: {10, 12, 21, 22, 31, 33, 42, 43, 52, 54, 63, 64, 73, 75, 84, 85 }
35
33
3
Returns: {1, 2, 17, 19, 34, 35 }
98
96
3
Returns: {1, 2, 49, 50, 97, 98 }
21
13
4
Returns: { }
10
8
3
Returns: {1, 2, 5, 6, 9, 10 }
38
72
2
Returns: {1, 2, 37, 38 }
48
93
2
Returns: { }
69
27
6
Returns: { }
40
11
8
Returns: { }
95
11
18
Returns: { }
34
4
17
Returns: {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 }
36
68
2
Returns: {1, 2, 35, 36 }
12
7
4
Returns: { }
34
8
9
Returns: {1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 29, 30, 33, 34 }
29
7
7
Returns: {7, 8, 10, 12, 14, 15, 17, 19, 21, 22, 24, 26, 28, 29 }
39
10
2
Returns: {33, 34, 38, 39 }
56
6
7
Returns: {37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56 }
53
14
8
Returns: {3, 4, 10, 11, 17, 18, 24, 25, 31, 32, 38, 39, 45, 46, 52, 53 }
41
5
5
Returns: {30, 31, 32, 34, 35, 36, 37, 39, 40, 41 }
34
7
8
Returns: {8, 10, 12, 13, 15, 17, 19, 20, 22, 24, 26, 27, 29, 31, 33, 34 }
37
6
2
Returns: {33, 34, 36, 37 }
39
12
3
Returns: {26, 27, 32, 33, 38, 39 }
54
12
6
Returns: {23, 24, 29, 30, 35, 36, 41, 42, 47, 48, 53, 54 }
42
5
16
Returns: {3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 40, 41, 42 }
69
6
13
Returns: {32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 65, 66, 68, 69 }
58
7
16
Returns: {4, 6, 8, 9, 11, 13, 15, 16, 18, 20, 22, 23, 25, 27, 29, 30, 32, 34, 36, 37, 39, 41, 43, 44, 46, 48, 50, 51, 53, 55, 57, 58 }
75
11
10
Returns: {24, 26, 30, 31, 35, 37, 41, 42, 46, 48, 52, 53, 57, 59, 63, 64, 68, 70, 74, 75 }
66
6
18
Returns: {14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 65, 66 }
65
9
10
Returns: {23, 25, 28, 29, 32, 34, 37, 38, 41, 43, 46, 47, 50, 52, 55, 56, 59, 61, 64, 65 }
68
13
10
Returns: {8, 10, 15, 16, 21, 23, 28, 29, 34, 36, 41, 42, 47, 49, 54, 55, 60, 62, 67, 68 }
64
10
13
Returns: {3, 4, 8, 9, 13, 14, 18, 19, 23, 24, 28, 29, 33, 34, 38, 39, 43, 44, 48, 49, 53, 54, 58, 59, 63, 64 }
62
7
14
Returns: {15, 17, 19, 20, 22, 24, 26, 27, 29, 31, 33, 34, 36, 38, 40, 41, 43, 45, 47, 48, 50, 52, 54, 55, 57, 59, 61, 62 }
60
8
13
Returns: {11, 12, 15, 16, 19, 20, 23, 24, 27, 28, 31, 32, 35, 36, 39, 40, 43, 44, 47, 48, 51, 52, 55, 56, 59, 60 }
66
10
12
Returns: {10, 11, 15, 16, 20, 21, 25, 26, 30, 31, 35, 36, 40, 41, 45, 46, 50, 51, 55, 56, 60, 61, 65, 66 }
96
10
16
Returns: {20, 21, 25, 26, 30, 31, 35, 36, 40, 41, 45, 46, 50, 51, 55, 56, 60, 61, 65, 66, 70, 71, 75, 76, 80, 81, 85, 86, 90, 91, 95, 96 }
100
7
20
Returns: {32, 34, 36, 37, 39, 41, 43, 44, 46, 48, 50, 51, 53, 55, 57, 58, 60, 62, 64, 65, 67, 69, 71, 72, 74, 76, 78, 79, 81, 83, 85, 86, 88, 90, 92, 93, 95, 97, 99, 100 }
97
7
25
Returns: {12, 13, 15, 17, 19, 20, 22, 24, 26, 27, 29, 31, 33, 34, 36, 38, 40, 41, 43, 45, 47, 48, 50, 52, 54, 55, 57, 59, 61, 62, 64, 66, 68, 69, 71, 73, 75, 76, 78, 80, 82, 83, 85, 87, 89, 90, 92, 94, 96, 97 }
93
9
19
Returns: {11, 12, 15, 17, 20, 21, 24, 26, 29, 30, 33, 35, 38, 39, 42, 44, 47, 48, 51, 53, 56, 57, 60, 62, 65, 66, 69, 71, 74, 75, 78, 80, 83, 84, 87, 89, 92, 93 }
93
6
28
Returns: {11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 65, 66, 68, 69, 71, 72, 74, 75, 77, 78, 80, 81, 83, 84, 86, 87, 89, 90, 92, 93 }
100
6
19
Returns: {45, 46, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 66, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 90, 91, 93, 94, 96, 97, 99, 100 }
99
8
20
Returns: {22, 23, 26, 27, 30, 31, 34, 35, 38, 39, 42, 43, 46, 47, 50, 51, 54, 55, 58, 59, 62, 63, 66, 67, 70, 71, 74, 75, 78, 79, 82, 83, 86, 87, 90, 91, 94, 95, 98, 99 }
98
8
15
Returns: {41, 42, 45, 46, 49, 50, 53, 54, 57, 58, 61, 62, 65, 66, 69, 70, 73, 74, 77, 78, 81, 82, 85, 86, 89, 90, 93, 94, 97, 98 }
92
8
19
Returns: {19, 20, 23, 24, 27, 28, 31, 32, 35, 36, 39, 40, 43, 44, 47, 48, 51, 52, 55, 56, 59, 60, 63, 64, 67, 68, 71, 72, 75, 76, 79, 80, 83, 84, 87, 88, 91, 92 }
90
7
25
Returns: {5, 6, 8, 10, 12, 13, 15, 17, 19, 20, 22, 24, 26, 27, 29, 31, 33, 34, 36, 38, 40, 41, 43, 45, 47, 48, 50, 52, 54, 55, 57, 59, 61, 62, 64, 66, 68, 69, 71, 73, 75, 76, 78, 80, 82, 83, 85, 87, 89, 90 }
100
6
16
Returns: {54, 55, 57, 58, 60, 61, 63, 64, 66, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 90, 91, 93, 94, 96, 97, 99, 100 }
90
11
17
Returns: {1, 2, 6, 8, 12, 13, 17, 19, 23, 24, 28, 30, 34, 35, 39, 41, 45, 46, 50, 52, 56, 57, 61, 63, 67, 68, 72, 74, 78, 79, 83, 85, 89, 90 }
97
10
20
Returns: {1, 2, 6, 7, 11, 12, 16, 17, 21, 22, 26, 27, 31, 32, 36, 37, 41, 42, 46, 47, 51, 52, 56, 57, 61, 62, 66, 67, 71, 72, 76, 77, 81, 82, 86, 87, 91, 92, 96, 97 }
94
8
24
Returns: {1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 29, 30, 33, 34, 37, 38, 41, 42, 45, 46, 49, 50, 53, 54, 57, 58, 61, 62, 65, 66, 69, 70, 73, 74, 77, 78, 81, 82, 85, 86, 89, 90, 93, 94 }
92
12
16
Returns: {1, 2, 7, 8, 13, 14, 19, 20, 25, 26, 31, 32, 37, 38, 43, 44, 49, 50, 55, 56, 61, 62, 67, 68, 73, 74, 79, 80, 85, 86, 91, 92 }
98
8
25
Returns: {1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 29, 30, 33, 34, 37, 38, 41, 42, 45, 46, 49, 50, 53, 54, 57, 58, 61, 62, 65, 66, 69, 70, 73, 74, 77, 78, 81, 82, 85, 86, 89, 90, 93, 94, 97, 98 }
100
7
29
Returns: {1, 2, 4, 6, 8, 9, 11, 13, 15, 16, 18, 20, 22, 23, 25, 27, 29, 30, 32, 34, 36, 37, 39, 41, 43, 44, 46, 48, 50, 51, 53, 55, 57, 58, 60, 62, 64, 65, 67, 69, 71, 72, 74, 76, 78, 79, 81, 83, 85, 86, 88, 90, 92, 93, 95, 97, 99, 100 }
95
6
32
Returns: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95 }
92
10
19
Returns: {1, 2, 6, 7, 11, 12, 16, 17, 21, 22, 26, 27, 31, 32, 36, 37, 41, 42, 46, 47, 51, 52, 56, 57, 61, 62, 66, 67, 71, 72, 76, 77, 81, 82, 86, 87, 91, 92 }
100
14
15
Returns: {1, 2, 8, 9, 15, 16, 22, 23, 29, 30, 36, 37, 43, 44, 50, 51, 57, 58, 64, 65, 71, 72, 78, 79, 85, 86, 92, 93, 99, 100 }
94
13
11
Returns: {28, 29, 34, 36, 41, 42, 47, 49, 54, 55, 60, 62, 67, 68, 73, 75, 80, 81, 86, 88, 93, 94 }
97
36
6
Returns: {6, 7, 24, 25, 42, 43, 60, 61, 78, 79, 96, 97 }
92
12
11
Returns: {31, 32, 37, 38, 43, 44, 49, 50, 55, 56, 61, 62, 67, 68, 73, 74, 79, 80, 85, 86, 91, 92 }
97
13
12
Returns: {24, 26, 31, 32, 37, 39, 44, 45, 50, 52, 57, 58, 63, 65, 70, 71, 76, 78, 83, 84, 89, 91, 96, 97 }
92
32
6
Returns: {11, 12, 27, 28, 43, 44, 59, 60, 75, 76, 91, 92 }
92
16
9
Returns: {27, 28, 35, 36, 43, 44, 51, 52, 59, 60, 67, 68, 75, 76, 83, 84, 91, 92 }
100
12
16
Returns: {9, 10, 15, 16, 21, 22, 27, 28, 33, 34, 39, 40, 45, 46, 51, 52, 57, 58, 63, 64, 69, 70, 75, 76, 81, 82, 87, 88, 93, 94, 99, 100 }
91
16
6
Returns: {50, 51, 58, 59, 66, 67, 74, 75, 82, 83, 90, 91 }
93
15
12
Returns: {9, 11, 17, 18, 24, 26, 32, 33, 39, 41, 47, 48, 54, 56, 62, 63, 69, 71, 77, 78, 84, 86, 92, 93 }
95
14
6
Returns: {59, 60, 66, 67, 73, 74, 80, 81, 87, 88, 94, 95 }
100
18
6
Returns: {54, 55, 63, 64, 72, 73, 81, 82, 90, 91, 99, 100 }
93
25
8
Returns: {4, 6, 17, 18, 29, 31, 42, 43, 54, 56, 67, 68, 79, 81, 92, 93 }
96
15
9
Returns: {35, 36, 42, 44, 50, 51, 57, 59, 65, 66, 72, 74, 80, 81, 87, 89, 95, 96 }
92
13
9
Returns: {39, 40, 45, 47, 52, 53, 58, 60, 65, 66, 71, 73, 78, 79, 84, 86, 91, 92 }
100
19
9
Returns: {23, 24, 32, 34, 42, 43, 51, 53, 61, 62, 70, 72, 80, 81, 89, 91, 99, 100 }
95
15
8
Returns: {41, 43, 49, 50, 56, 58, 64, 65, 71, 73, 79, 80, 86, 88, 94, 95 }
99
23
8
Returns: {17, 19, 29, 30, 40, 42, 52, 53, 63, 65, 75, 76, 86, 88, 98, 99 }
90
13
10
Returns: {30, 32, 37, 38, 43, 45, 50, 51, 56, 58, 63, 64, 69, 71, 76, 77, 82, 84, 89, 90 }
92
12
13
Returns: {19, 20, 25, 26, 31, 32, 37, 38, 43, 44, 49, 50, 55, 56, 61, 62, 67, 68, 73, 74, 79, 80, 85, 86, 91, 92 }
91
22
6
Returns: {35, 36, 46, 47, 57, 58, 68, 69, 79, 80, 90, 91 }
91
20
8
Returns: {20, 21, 30, 31, 40, 41, 50, 51, 60, 61, 70, 71, 80, 81, 90, 91 }
97
17
10
Returns: {19, 21, 28, 29, 36, 38, 45, 46, 53, 55, 62, 63, 70, 72, 79, 80, 87, 89, 96, 97 }
95
22
6
Returns: {39, 40, 50, 51, 61, 62, 72, 73, 83, 84, 94, 95 }
95
17
6
Returns: {51, 53, 60, 61, 68, 70, 77, 78, 85, 87, 94, 95 }
90
26
6
Returns: {24, 25, 37, 38, 50, 51, 63, 64, 76, 77, 89, 90 }
94
33
6
Returns: {10, 12, 27, 28, 43, 45, 60, 61, 76, 78, 93, 94 }
96
12
7
Returns: {59, 60, 65, 66, 71, 72, 77, 78, 83, 84, 89, 90, 95, 96 }
90
12
11
Returns: {29, 30, 35, 36, 41, 42, 47, 48, 53, 54, 59, 60, 65, 66, 71, 72, 77, 78, 83, 84, 89, 90 }
95
24
7
Returns: {22, 23, 34, 35, 46, 47, 58, 59, 70, 71, 82, 83, 94, 95 }
98
16
10
Returns: {25, 26, 33, 34, 41, 42, 49, 50, 57, 58, 65, 66, 73, 74, 81, 82, 89, 90, 97, 98 }
100
1
1
Returns: {99, 100 }
100
3
2
Returns: { }
100
5
40
Returns: {1, 3, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 35, 36, 38, 39, 40, 41, 43, 44, 45, 46, 48, 49, 50, 51, 53, 54, 55, 56, 58, 59, 60, 61, 63, 64, 65, 66, 68, 69, 70, 71, 73, 74, 75, 76, 78, 79, 80, 81, 83, 84, 85, 86, 88, 89, 90, 91, 93, 94, 95, 96, 98, 99, 100 }
20
1
1
Returns: {19, 20 }
2
1
1
Returns: {1, 2 }
10
1
4
Returns: { }
6
1
1
Returns: {5, 6 }
100
2
1
Returns: {99, 100 }
12
2
3
Returns: { }
4
4
4
Returns: { }
100
3
1
Returns: {99, 100 }
10
2
1
Returns: {9, 10 }
2
2
1
Returns: {1, 2 }
50
3
5
Returns: { }
2
3
5
Returns: { }
2
100
1
Returns: {1, 2 }
50
3
8
Returns: { }
4
3
2
Returns: { }
7
3
2
Returns: { }
5
1
1
Returns: {4, 5 }
5
5
2
Returns: {1, 3, 4, 5 }
100
3
3
Returns: { }
30
1
5
Returns: { }
64
2
18
Returns: { }
100
4
100
Returns: { }
50
1
5
Returns: { }
67
1
45
Returns: { }
100
5
3
Returns: {94, 95, 96, 98, 99, 100 }
15
1
3
Returns: { }
8
1
2
Returns: { }
100
7
4
Returns: {88, 90, 92, 93, 95, 97, 99, 100 }
10
10
1
Returns: {9, 10 }
10
5
2
Returns: {6, 8, 9, 10 }
90
100
2
Returns: {39, 40, 89, 90 }
100
19
5
Returns: {61, 62, 70, 72, 80, 81, 89, 91, 99, 100 }
5
6
2
Returns: {1, 2, 4, 5 }
10
3
2
Returns: { }
5
5
5
Returns: { }
100
100
1
Returns: {99, 100 }
100
1
2
Returns: { }
100
1
3
Returns: { }
1
1
1
Returns: { }
30
1
1
Returns: {29, 30 }
5
2
2
Returns: { }
4
2
2
Returns: { }
3
3
1
Returns: {2, 3 }
10
1
2
Returns: { }
6
7
2
Returns: {1, 3, 5, 6 }
100
2
2
Returns: { }
50
3
10
Returns: { }
31
19
4
Returns: {1, 3, 11, 12, 20, 22, 30, 31 }
6
2
2
Returns: { }
10
1
1
Returns: {9, 10 }
100
2
5
Returns: { }
20
7
4
Returns: {8, 10, 12, 13, 15, 17, 19, 20 }