Problem Statement
Before mechanical clocks were common, people used hourglasses to measure time. An hourglass has two sections connected with a thin passage, where sand trickles through. If all the sand is at the bottom section, you may flip the glass and the sand will start trickling from the top section to the bottom section. After some time (the duration of that specific hourglass) all sand will have reached the bottom section again.
Having only one hourglass limits you to measuring times that are multiples of the duration of the hourglass, but with two hourglasses, one can measure many more times. For instance, if one hourglass has duration 5 minutes and the other 7 minutes, you can measure 9 minutes by the following procedure (at time 0, both hourglasses have all their sand at the bottom): Flip both hourglasses at time 0; after 5 minutes turn the 5-minute glass; after another 2 minutes (when the 7-minute glass is done) turn the 5 minute glass again, which will then run for 2 minutes, thus totalling 9 minutes.
Given the duration of the two hourglasses, calculate the 10 shortest time periods you can measure with these two hourglasses using only the following rules:
- At time 0, both hourglasses have all their sand in one side.
- An hourglass may only be flipped at time 0, or precisely when one of the hourglasses have run out of sand.
- Measurable times include all times when an hourglass has just run out of sand.
Create a class HourGlass containing the method measurable taking an
Definition
- Class:
- HourGlass
- Method:
- measurable
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] measurable(int glass1, int glass2)
- (be sure your method is public)
Notes
- You may not turn an hourglass on its side.
Constraints
- glass1 will be between 1 and 50, inclusive.
- glass2 will be between 1 and 50, inclusive.
Examples
5
7
Returns: { 5, 7, 9, 10, 11, 12, 13, 14, 15, 16 }
5, 7, 10, 14 and 15 can of course be measured since these times are just multiples of single hourglasses, and 12 is the sum of the two hourglasses, so it's also easy to measure. 9, 11 and 13 can be measured according to the following scheme: Time Sand Action Sand 0 0 0 Flip both 7 5 5 2 0 Flip 5-min 2 5 7 0 3 Flip both 7 2 9 5 0 Flip both 2 5 11 0 3 Flip both 7 2 13 5 0
13
5
Returns: { 5, 10, 13, 15, 16, 17, 18, 19, 20, 21 }
23
23
Returns: { 23, 46, 69, 92, 115, 138, 161, 184, 207, 230 }
Since the hourglasses are identical, it's not possible to measure times other than those that are multiples of the duration of the hourglasses.
24
30
Returns: { 24, 30, 36, 42, 48, 54, 60, 66, 72, 78 }
1
50
Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
19
6
Returns: { 6, 12, 18, 19, 20, 21, 22, 23, 24, 25 }
27
21
Returns: { 21, 27, 33, 39, 42, 45, 48, 51, 54, 57 }
50
50
Returns: { 50, 100, 150, 200, 250, 300, 350, 400, 450, 500 }
1
1
Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
45
20
Returns: { 20, 40, 45, 50, 55, 60, 65, 70, 75, 80 }
19
8
Returns: { 8, 16, 19, 22, 24, 25, 27, 28, 29, 30 }
50
48
Returns: { 48, 50, 52, 54, 56, 58, 60, 62, 64, 66 }
47
13
Returns: { 13, 26, 39, 47, 52, 55, 57, 60, 62, 63 }
19
24
Returns: { 19, 24, 29, 34, 38, 39, 43, 44, 48, 49 }
20
23
Returns: { 20, 23, 26, 29, 32, 35, 38, 40, 41, 43 }
8
11
Returns: { 8, 11, 14, 16, 17, 19, 20, 21, 22, 23 }
2
5
Returns: { 2, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
2
3
Returns: { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
50
17
Returns: { 17, 34, 50, 51, 52, 53, 54, 55, 56, 57 }
10
48
Returns: { 10, 20, 30, 40, 48, 50, 52, 54, 56, 58 }
14
18
Returns: { 14, 18, 22, 26, 28, 30, 32, 34, 36, 38 }
46
46
Returns: { 46, 92, 138, 184, 230, 276, 322, 368, 414, 460 }
10
14
Returns: { 10, 14, 18, 20, 22, 24, 26, 28, 30, 32 }
19
23
Returns: { 19, 23, 27, 31, 35, 38, 39, 42, 43, 46 }
29
20
Returns: { 20, 29, 38, 40, 47, 49, 51, 56, 58, 60 }
27
18
Returns: { 18, 27, 36, 45, 54, 63, 72, 81, 90, 99 }
50
41
Returns: { 41, 50, 59, 68, 77, 82, 86, 91, 95, 100 }
48
41
Returns: { 41, 48, 55, 62, 69, 76, 82, 83, 89, 90 }
1
2
Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
49
50
Returns: { 49, 50, 51, 52, 53, 54, 55, 56, 57, 58 }
7
12
Returns: { 7, 12, 14, 16, 17, 18, 19, 20, 21, 22 }
50
17
Returns: { 17, 34, 50, 51, 52, 53, 54, 55, 56, 57 }
13
5
Returns: { 5, 10, 13, 15, 16, 17, 18, 19, 20, 21 }
5
7
Returns: { 5, 7, 9, 10, 11, 12, 13, 14, 15, 16 }
5
13
Returns: { 5, 10, 13, 15, 16, 17, 18, 19, 20, 21 }