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:
- LockersDivTwo
- 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 10000, inclusive.
Examples
9
Returns: 6
The example from the problem statement.
42
Returns: 42
314
Returns: 282
10000
Returns: 9894
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
77
Returns: 60
101
Returns: 82
239
Returns: 214
321
Returns: 282
497
Returns: 454
717
Returns: 672
779
Returns: 732
989
Returns: 930
1277
Returns: 1212
1631
Returns: 1558
2039
Returns: 1932
3053
Returns: 2940
3233
Returns: 3102
3971
Returns: 3814
5231
Returns: 5014
6833
Returns: 6534
34
Returns: 34
132
Returns: 132
282
Returns: 282
510
Returns: 510
802
Returns: 802
1174
Returns: 1174
1558
Returns: 1558
2058
Returns: 2058
2602
Returns: 2602
3234
Returns: 3234
3814
Returns: 3814
4582
Returns: 4582
5398
Returns: 5398
6318
Returns: 6318
7114
Returns: 7114
8160
Returns: 8160
9192
Returns: 9192
4709
Returns: 4582
1032
Returns: 1002
7735
Returns: 7714
9639
Returns: 9618
1773
Returns: 1770
7347
Returns: 7272
6708
Returns: 6534
2999
Returns: 2940
985
Returns: 930
5150
Returns: 5014
8792
Returns: 8760
8986
Returns: 8910
4646
Returns: 4582
9433
Returns: 9192
1592
Returns: 1558
8282
Returns: 8160
2939
Returns: 2922
9062
Returns: 9012
567
Returns: 540
159
Returns: 154
569
Returns: 540
9170
Returns: 9118
9685
Returns: 9618
4609
Returns: 4582
4583
Returns: 4582
6472
Returns: 6432
6452
Returns: 6432
8995
Returns: 8910
5231
Returns: 5014
2032
Returns: 1932
7807
Returns: 7800
5052
Returns: 5014
9016
Returns: 9012
7709
Returns: 7558
455
Returns: 454
7174
Returns: 7114
4027
Returns: 4018
3274
Returns: 3234
3236
Returns: 3234
2523
Returns: 2494
3213
Returns: 3102
9999
Returns: 9894
36
Returns: 34
1893
Returns: 1882
9876
Returns: 9840
9998
Returns: 9894
1000
Returns: 990
7777
Returns: 7714
420
Returns: 418
9997
Returns: 9894
600
Returns: 570
125
Returns: 118
7172
Returns: 7114
2736
Returns: 2718
9898
Returns: 9894