Problem Statement
A hallway is filled with lockers numbered 1 through N, initially all closed. Out of boredom, Dave and Earl decide to open all the lockers. They make multiple passes through the hallway, each beginning at locker 1. On the first pass, they open the first unopened locker, and every second unopened locker thereafter. On the second pass, they open the first unopened locker, and every third unopened locker thereafter. In general, on the nth pass, they open the first unopened locker, and every (n+1)th unopened locker thereafter.
For example, with 9 lockers, on the first pass they open 1, 3, 5, 7, and 9, leaving 2, 4, 6, and 8. On the second pass they open 2 and 8, leaving 4 and 6. On the third pass they open locker 4, and on the final pass locker 6.
You will be given N, the number of lockers. Return the number of the locker opened last.
Definition
- Class:
- LockersDivOne
- Method:
- lastOpened
- Parameters:
- int
- Returns:
- int
- Method signature:
- int lastOpened(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 2000000, inclusive.
Examples
9
Returns: 6
The example from the problem statement.
42
Returns: 42
314
Returns: 282
2000000
Returns: 1999854
1
Returns: 1
2
Returns: 2
3
Returns: 2
4
Returns: 4
5
Returns: 4
6
Returns: 6
7
Returns: 6
8
Returns: 6
10
Returns: 10
11
Returns: 10
12
Returns: 12
17
Returns: 12
29
Returns: 22
57
Returns: 48
101
Returns: 82
321
Returns: 282
717
Returns: 672
989
Returns: 930
1631
Returns: 1558
3053
Returns: 2940
3971
Returns: 3814
6833
Returns: 6534
25739
Returns: 25198
74021
Returns: 73272
94277
Returns: 93274
118679
Returns: 117552
199661
Returns: 197988
345993
Returns: 343920
460181
Returns: 457798
735561
Returns: 732612
765317
Returns: 762090
833267
Returns: 828048
802
Returns: 802
7114
Returns: 7114
19872
Returns: 19872
39018
Returns: 39018
64632
Returns: 64632
96312
Returns: 96312
134898
Returns: 134898
179062
Returns: 179062
230532
Returns: 230532
286974
Returns: 286974
351210
Returns: 351210
420942
Returns: 420942
497958
Returns: 497958
580218
Returns: 580218
669874
Returns: 669874
765322
Returns: 765322
866842
Returns: 866842
975678
Returns: 975678
1088970
Returns: 1088970
1210102
Returns: 1210102
1338958
Returns: 1338958
1471258
Returns: 1471258
1611898
Returns: 1611898
1757172
Returns: 1757172
1912002
Returns: 1912002
1991418
Returns: 1991418
1875321
Returns: 1871958
1920904
Returns: 1919502
1896379
Returns: 1894428
1244146
Returns: 1242828
454224
Returns: 453102
1167427
Returns: 1167270
528500
Returns: 526618
1333468
Returns: 1330978
422925
Returns: 422602
1644440
Returns: 1642932
256900
Returns: 256788
809308
Returns: 809280
1033672
Returns: 1032658
39409
Returns: 39300
1865925
Returns: 1864470
72827
Returns: 72718
1793954
Returns: 1792512
22458
Returns: 22278
1368982
Returns: 1368960
255031
Returns: 254434
275027
Returns: 274174
23537
Returns: 23502
1280635
Returns: 1280352
981867
Returns: 981690
1806794
Returns: 1806132
70235
Returns: 70174
1378524
Returns: 1378188
1860626
Returns: 1859338
670982
Returns: 670758
1482497
Returns: 1481052
423800
Returns: 422602
1520612
Returns: 1518798
1638684
Returns: 1637982
1958076
Returns: 1956238
11386
Returns: 11302
1345687
Returns: 1345462
974465
Returns: 972108
56151
Returns: 56010
1500836
Returns: 1499262
784431
Returns: 784200
1705022
Returns: 1702080
1240589
Returns: 1240572
1768731
Returns: 1767222
964835
Returns: 963798
1792140
Returns: 1790982
1906351
Returns: 1903462
889195
Returns: 888330
1768921
Returns: 1767222
1121613
Returns: 1120368
1556163
Returns: 1555558
1979797
Returns: 1976482
1999999
Returns: 1999854
1999854
Returns: 1999854
1876437
Returns: 1875588
134567
Returns: 133702
1234561
Returns: 1232448
619931
Returns: 619902
1999123
Returns: 1998852
1999923
Returns: 1999854
1999853
Returns: 1998852
18468
Returns: 18414
1987567
Returns: 1985988
55
Returns: 48
100
Returns: 82