PROBLEM LINK:
DIFFICULTY:
CAKEWALK
PROBLEM:
Given integers X and Y. Determine the minimum number of moves required to change X to Y, where in one move, you can either add 2 or subtract 1 from X.
EXPLANATION:
A simple problem, with a little casework:
Y \le X - In this case, Chef has to go X-Y steps backwards, from his current position. Since he can go only one step backwards in each move, the minimum number of moves required is thus X-Y.
Y > X - Here, Chef has to go Y-X steps forward, from his current position.
When Y-X is even, Chef can make exactly \frac{Y-X}{2} forward moves (since each forward move takes him two steps ahead) to reach Y.
When Y-X is odd, Chef can make \frac{Y-X+1}{2} forward moves (taking him to Y+1), followed by 1 backward move (taking him to Y).
It can be trivially deduced that no better sequence of moves exists.
TIME COMPLEXITY:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters