package Ġmedium Ċ Ċ class Ġ_ 6 5 0 Two Keys Keyboard Ġ{ ĊĠĠĠ Ġclass ĠSolution Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġmin Steps ( n : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdp Ġ= ĠInt Array ( n Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 2 .. n ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= ĠInt . MAX _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ* Ġj Ġ<= Ġi ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ% Ġj Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= ĠMath . min ( dp [ i ], Ġdp [ j ] Ġ+ Ġi Ġ/ Ġj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= ĠMath . min ( dp [ i ], Ġdp [ i Ġ/ Ġj ] Ġ+ Ġj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġdp [ n ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġclass ĠBest Solution Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġmin Steps ( n : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġans Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġtemp N Ġ= Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ* Ġi Ġ<= Ġtemp N ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( temp N Ġ% Ġi Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtemp N Ġ/= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġans Ġ+= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( temp N Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġans Ġ+= Ġtemp N ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġans ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ }