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
{8,40}
2
0
20
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.
{8,24,40}
2
0
20
Returns: 8
With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
{8,24,40}
3
0
100
Returns: 4
3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
{-10,10}
2
2
26
Returns: 10
Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
{-20,10,-40,40}
2
9
11
Returns: 1
{-1,2,3,4,5}
3
10000
50000
Returns: 53333
{-1,1}
2
0
50000
Returns: 200001
{-2,91,87,77,71}
4
0
50000000
Returns: 1471
{100,97,93,91,89}
5
0
50000000
Returns: 1
{81,53,32,71,-15}
4
20653
43090
Returns: 0
{34,82,95,41,-66}
5
2447
34805
Returns: 0
{-75,-44,-91,80,66}
4
13173
24970
Returns: 2
{-92,47,-37,38,-62}
5
10073
40784
Returns: 0
{-20,61,-21,-22,99}
4
28208
51341
Returns: 4
{48,-8,-37,-71,-65}
3
2101
8954
Returns: 43
{22,-89,-54,17,28}
2
20344
40362
Returns: 16873
{-58,-75,90,67,82}
2
16807
28015
Returns: 4017
{5,-67,14,-63,10}
4
15643
17093
Returns: 6
{-72,50,3,-14,-70}
4
32037
33085
Returns: 3
{-14,62,75,36,52}
2
24986
57437
Returns: 26346
{-47,-62,-68,23,80}
3
19868
24079
Returns: 3
{25,63,-98,-29,-27}
4
10666
27270
Returns: 0
{84,29,-2,31,61}
3
21738
46502
Returns: 130
{4,-28,16,56,-31}
3
29751
50137
Returns: 872
{-72,85,-5,-38,-58}
2
2384
24119
Returns: 37743
{-76,93,84,-37,73}
5
28991
41733
Returns: 0
{-47,19,79,-70,11}
3
7316
27520
Returns: 27
{25,-7,-38,4,-17}
4
16533
38083
Returns: 40
{-91,15,8,7,56}
5
29796
53939
Returns: 4
{-38,-69,-27,75,45}
2
3647
23520
Returns: 12216
{91,71,69,-28,-35}
4
12856
28376
Returns: 0
{20,67,95,-74,-46}
5
10834
21315
Returns: 0
{1,64,68,80,-9}
4
22125
43535
Returns: 28
{-66,65,-70,75,-87}
4
11635
39707
Returns: 0
{76,64,52,57,35}
4
15299
34904
Returns: 1
{76,82,3,58,-96}
4
19165
28277
Returns: 1
{56,64,41,44,-69}
2
7758
39688
Returns: 10771
{67,90,-20,24,-11}
5
29150
57397
Returns: 0
{14,-80,-83,89,-33}
2
9464
28114
Returns: 16752
{-48,4,69,48,-23}
2
16217
30741
Returns: 34153
{64,-74,19,57,-92}
4
15100
21434
Returns: 0
{25,85,-50,100,-13}
4
16196
44969
Returns: 146
{16,-34,67,87,-65}
2
14699
37921
Returns: 19869
{-96,91,9,33,-8}
5
5040
28059
Returns: 0
{-36,-16}
2
22356
46186
Returns: 1655
{-41,-24}
2
6069
19484
Returns: 464
{78,-48}
2
16130
38670
Returns: 1517
{78,49}
2
29280
60038
Returns: 467
{14,-74}
2
16734
27023
Returns: 1748
{-91,100}
2
9174
21162
Returns: 503
{-34,94}
2
24131
33958
Returns: 788
{74,-39}
2
20873
40982
Returns: 1575
{-62,86}
2
32119
55231
Returns: 1283
{-81,2}
2
3605
5537
Returns: 1979
{-18,-73}
2
1071
5324
Returns: 356
{-26,-47}
2
8258
22779
Returns: 499
{65,67}
2
23484
43415
Returns: 18
{-70,55}
2
1474
10672
Returns: 597
{-26,95}
2
2326
24997
Returns: 2222
{16,-20}
2
2295
16107
Returns: 3108
{99,-64}
2
8472
20905
Returns: 640
{5,49}
2
14577
18304
Returns: 1339
{-15,4,41,-68,-89}
2
21197240
24512033
Returns: 8881260
{-79,98,97,-61,72}
2
27725288
31314259
Returns: 1198720
{-74,34,-17,64,14}
3
21426840
45236960
Returns: 463035
{41,-78,-99,91,-93}
2
26707385
46649025
Returns: 7644243
{9,-55,-48,-62,94}
2
8269810
11996255
Returns: 4350340
{1,2,4,8,97}
2
0
50000000
Returns: 355927839
{1,2,4,8,97}
3
0
50000000
Returns: 25773197
{1,3,9,27,-97}
2
0
50000000
Returns: 372508589
{1,4,16,64,-99}
2
0
50000000
Returns: 379513892
{1,4,16,64,-16}
3
0
50000000
Returns: 25000001
{-1,-2,1,2,3}
2
0
50000000
Returns: 433333335
Quite large answer (possibly max).
{8,40}
2
10
10
Returns: 1
{-2, 91, 87, 77, 71 }
4
0
50000000
Returns: 1471
{97, 93, 89, 83, 79 }
2
575757
47474747
Returns: 1118323
{-2, 91, 87, 77, 71 }
5
0
50000000
Returns: 9
{2, 5, 30, 47, 94 }
3
10121
12211312
Returns: 1176853