Problem Statement |
| | A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.
|
| |
Definition |
| | | Class: | KPlanetaryAlignment | | Method: | number | | Parameters: | int[], int, int, int | | Returns: | int | | Method signature: | int number(int[] periods, int k, int T1, int T2) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The constraints ensure the return value will fit in a signed 32-bit integer. |
| - | Alignments can occur with the planets either on the same side of the star or diametrically opposite each other. |
| - | The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer. |
| |
Constraints |
| - | periods will contain between 2 and 5 elements, inclusive. |
| - | Each element of periods will be a non-zero integer between -100 and 100, inclusive. |
| - | The elements of periods will be distinct. |
| - | k will be between 2 and the number of elements in periods, inclusive. |
| - | T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive. |
| - | T1 will be between 0 and T2, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 5 | | Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20. |
|
|
| 1) | |
| | | Returns: 8 | | With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20. |
|
|
| 2) | |
| | | Returns: 4 | | 3-alignments of the same set of planets happen at T = 0, 30, 60, 90. |
|
|
| 3) | |
| | | Returns: 10 | | Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds. |
|
|
| 4) | |
| | |
| 5) | |
| | |
| 6) | |
| | {-2,91,87,77,71} | 4 | 0 | 50000000 |
| Returns: 1471 | |
|