Problem Statement
Peter is writing a thesis. He's not really a technical type, so he's using a text editor and his whole thesis is one huge file. The file contains N pages, numbered from 0 to N-1. The number N is even.
Exactly one half of the pages contain text and the other half contain images. Currently, the pages with images have numbers of the form ((A + i * B) mod N) where 0 <= i < N/2. (It is guaranteed that these are N/2 different pages.)
For example, if N = 10, A = 2 and B = 3, the image pages have the following numbers:
- (2 + 0*3) mod 10 = 2,
- (2 + 1*3) mod 10 = 5,
- (2 + 2*3) mod 10 = 8,
- (2 + 3*3) mod 10 = 11 mod 10 = 1, and
- (2 + 4*3) mod 10 = 14 mod 10 = 4.
Thus, there would be images on pages 1, 2, 4, 5, 8, and text on pages 0, 3, 6, 7, 9.
Watch out for integer overflow when computing the values (A + i * B).
Peter has now decided that he wants to rearrange his thesis into a more reader-friendly form: the pages should alternate between text and images. More precisely, the even-numbered pages (0, 2, 4, ...) should contain text and the odd-numbered pages (1, 3, 5, ...) should contain images.
The main issue now is the text editor. Haphazardly moving pages from place to place will break all formatting, references and such, and Peter does not want to spend ages fixing the document after each such edit. The only operation he's comfortable doing is swapping the order of two consecutive pages.
Compute and return the minimum number of such swaps Peter needs to make in order to rearrange his thesis into the desired pattern.
Definition
- Class:
- RearrangePages
- Method:
- countSwaps
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long countSwaps(int N, int A, int B)
- (be sure your method is public)
Notes
- The last constraint requires that B and N must be relatively prime. In other words, they must not have any common divisor other than 1. This constraint guarantees that the N/2 page numbers given in the problem statement are distinct.
Constraints
- N will be between 2 and 1,000,000, inclusive.
- N will be even.
- A will be between 0 and N-1, inclusive.
- B will be between 1 and N-1, inclusive.
- B and N will be relatively prime.
Examples
6
1
1
Returns: 3
The thesis has 6 pages. Pages with images are pages 1, 2, 3. Thus, the thesis now looks like this: "text, image, image, image, text, text". We can rearrange this thesis as follows: Swap the pages with current (0-based) indices 3 and 4. New thesis: "text, image, image, text, image, text". Swap the pages with current indices 4 and 5. New thesis: "text, image, image, text, text, image". Swap the pages with current indices 2 and 3. New thesis: "text, image, text, image, text, image" and we are done.
10
0
3
Returns: 5
The thesis has 10 pages. Pages with images are pages 0, 3, 6, 9, and (12 mod 10) = 2. Thus, currently the thesis looks as follows: image, text, image, image, text, text, image, text, text, image. If Peter chooses his swaps wisely, he can rearrange the pages of this thesis using five swaps.
10
5
1
Returns: 10
This thesis starts with five pages with text and then contains five pages with images. We need 10 swaps to rearrange it into "text, image, text, image, ...". Remember that we are only allowed to swap consecutive pages.
1000000
500000
1
Returns: 124999750000
1000000
0
1
Returns: 125000250000
1000000
0
500001
Returns: 250000
1000000
999999
999999
Returns: 124999750000
1000000
499999
999999
Returns: 125000250000
2
0
1
Returns: 1
2
1
1
Returns: 0
257308
189754
256115
Returns: 3496905
494886
236
452209
Returns: 485898
186282
75949
185279
Returns: 3066646
100020
41024
68507
Returns: 1261761
258332
207357
258331
Returns: 4356155161
89550
10482
89549
Returns: 642905372
469462
267499
15
Returns: 1395623937
555526
31959
470649
Returns: 866901
217780
107150
217699
Returns: 70871015
787416
638165
17
Returns: 2412732252
622794
516232
1519
Returns: 17419337
53016
2376
53015
Returns: 293966768
480140
397228
480131
Returns: 1753962753
71552
52655
8135
Returns: 52044
219416
137652
219411
Returns: 746594976
124242
96451
124241
Returns: 975447560
35616
30884
899
Returns: 139750
96426
463
17
Returns: 67124014
88422
80004
8977
Returns: 105010
39934
34612
3673
Returns: 60502
367850
276849
8187
Returns: 1182626
32480
19264
1
Returns: 91898520
41502
15455
39881
Returns: 83477
32180
6169
32179
Returns: 68235775
42152
13496
4405
Returns: 75346
41856
3370
23
Returns: 6963846
112288
34915
107995
Returns: 251200
24892
11207
24873
Returns: 3347415
387686
252770
166013
Returns: 2072974
748658
713832
3
Returns: 19412370543
251910
212736
1351
Returns: 3478422
422564
344446
3363
Returns: 3566945
22800
6075
7
Returns: 4661470
231984
41671
231893
Returns: 39861444
504462
422428
87889
Returns: 376852
126972
57306
125129
Returns: 887675
41774
31026
735
Returns: 155000
151342
36572
150237
Returns: 1329004
27298
22803
27295
Returns: 17331128
40546
20063
40325
Returns: 973104
69764
38181
3
Returns: 168075691
111712
104575
203
Returns: 5892798
227888
100096
13
Returns: 392580622
198794
90726
198745
Returns: 84084207
52042
19755
52041
Returns: 214781626
29002
14161
1
Returns: 100317850
146618
549
29
Returns: 91352374
91756
75342
18195
Returns: 148915
685766
678468
23
Returns: 2449138622
165256
34597
106199
Returns: 5484856
44168
28838
44079
Returns: 1588074
459726
2767
1
Returns: 25790236917
310558
172845
433
Returns: 22287985
935390
666553
902441
Returns: 2364993
31286
10958
31277
Returns: 7899818
128550
118384
13
Returns: 116664850
52740
38029
1
Returns: 176171375
777272
699480
757165
Returns: 4566350
205060
162861
146439
Returns: 2533451
116984
78580
15515
Returns: 160048
851134
65562
1193
Returns: 56296488
705780
278658
1
Returns: 41580233181
883756
70427
3
Returns: 23822885477
688530
147260
688397
Returns: 227430529
713112
317433
670435
Returns: 1694350
954986
607920
19
Returns: 3617520901
939748
743504
103
Returns: 550323449
879044
348919
13
Returns: 4997759581
972238
907171
879097
Returns: 904033
818564
219369
1003
Returns: 41911161
666988
28860
171
Returns: 274932495
888484
353009
31513
Returns: 1712111
758892
626983
1
Returns: 39337333139
704826
587403
1
Returns: 34504289298
928456
777893
355083
Returns: 1149010
922660
729356
922659
Returns: 54602223907
985984
246679
44775
Returns: 1910816
708594
148598
708589
Returns: 6439281617
959788
142052
7761
Returns: 8430755
989728
36216
237379
Returns: 2549130
1234
7
13
Returns: 13654
1000000
999997
999993
Returns: 17857250002
1000000
999998
999999
Returns: 124999250002
999988
831201
599993
Returns: 14264738663
1000000
345342
999997
Returns: 23863715252
1000000
999999
7
Returns: 17856250028