Problem Statement
There is nothing more beautiful than just an integer number.
You start with the integer 1 and you apply a sequence of operations until you reach the integer n. Each operation can be one of the following:
- Increment the current number by 1.
- If the current number is greater than 1, decrement it by 1.
- Raise the current number to any positive integral power.
Return the minimum possible number of operations required to reach n.
Definition
- Class:
- ThePower
- Method:
- count
- Parameters:
- long
- Returns:
- int
- Method signature:
- int count(long n)
- (be sure your method is public)
Constraints
- n will be between 1 and 10^18, inclusive.
Examples
8
Returns: 2
1. Increment by 1: 1 + 1 = 2. 2. Raise to the power of 3: 2^3 = 8.
1
Returns: 0
We don't need any operations here.
80
Returns: 4
1. Increment by 1: 1 + 1 = 2. 2. Increment by 1: 2 + 1 = 3. 3. Raise to the power of 4: 3^4 = 81. 4. Decrement by 1: 81 - 1 = 80.
123456789
Returns: 2566
9
Returns: 3
6
Returns: 4
8
Returns: 2
757148
Returns: 284
167851001
Returns: 6990
301413357
Returns: 9107
336971125
Returns: 8467
659598369
Returns: 18220
160567226
Returns: 12471
391749388
Returns: 13561
4890852
Returns: 2103
35766291
Returns: 5951
26239573
Returns: 4763
473038165
Returns: 19316
597007
Returns: 539
3615545
Returns: 1790
127087881097001
Returns: 1997580
101567597359932145
Returns: 66648872
105909879564288801
Returns: 86936154
1915987881158338
Returns: 15298266
938492141627881
Returns: 6466598
282406622136985
Returns: 8758385
1178853313121185
Returns: 23694898
46424149512186421
Returns: 154518906
6342560488447345
Returns: 11912811
113770165438317571
Returns: 6273084
649336441051022059
Returns: 65951639
9623522848888873
Returns: 38517834
1000000000000000000
Returns: 5
987654321987654321
Returns: 987819571
123456789123456789
Returns: 28210180
576460752303423488
Returns: 2
450283905890997363
Returns: 3
2
Returns: 1
3
Returns: 2
6
Returns: 4
7
Returns: 3
9
Returns: 3
10
Returns: 4
205891132094649
Returns: 3
205891132094640
Returns: 12
205891132094648
Returns: 4
999927087881096999
Returns: 551996889
999967597359931129
Returns: 902557479
999909879564287741
Returns: 466210115
999915987881158318
Returns: 116577458
999938492141627871
Returns: 804199087
999982406622136982
Returns: 544758576
999978853313121173
Returns: 798677735
999924149512185956
Returns: 73815750
999942560488447281
Returns: 336411595
999970165438316433
Returns: 784215379
657456423656735435
Returns: 392044814
98765432198765431
Returns: 197088682
689989689989689983
Returns: 617503811
1234567890
Returns: 29577
162614549655681
Returns: 10037
293456789123789457
Returns: 563241
987987987987987987
Returns: 407307109
232313131
Returns: 5554
999999999999998699
Returns: 1306
74747474747474747
Returns: 48256904
12345678901234678
Returns: 86421292
48151622342481516
Returns: 107712566
79792266297611998
Returns: 7
123456789987654321
Returns: 189679344
99979999999997
Returns: 1000798
954312123476543412
Returns: 705804666
12345678987654321
Returns: 1649
844145128075355872
Returns: 274277846
9277654329653407
Returns: 5481853
98765432112345678
Returns: 283508435
123456789876543218
Returns: 78568241
534223122313218976
Returns: 486102883