Coding Test Practice - Magic Elevator
It's a problem you can solve with DFS.
You can optimize further and solve it greedily in O(N),
but a DFS solution is pretty simple and kind of clever, so I brought it here.
(N: number of digits in stroey)
To turn stroey into 0,
by handling the last digit first
you can make it so there are two edges.
A. Dropping the last digit
B. Rounding up the last digit
After doing A and B, the trailing 0 isn't needed anymore, so
let's boldly erase it.
The time complexity can be analyzed in two ways.
If N is the number of digits in stroey, it's O(2^N),
and if N is the value of stroey, it's O(logN).
#include <string> #include <vector> using namespace std; int solution(int x) { if (x/10 == 0) return min(x, 10-x+1); return min(solution(x/10)+x%10, solution(x/10+1)+10-x%10); }
I think this is probably the best solution.
It's a problem where there's no need to overcomplicate things with greedy.