hardDynamic Programming 1DPure DSA~25 min
Fewest Days to Drain a Backlog
A worker drains a backlog of n items. Each day they may process exactly one item, or — if the remaining count is divisible — halve it, or cut it to one third. Find the fewest days to reach zero.
Problem
Given an integer n items, each day you may do exactly one of: process 1 item; if n is divisible by 2, process n/2 items (leaving n/2); if n is divisible by 3, process 2*n/3 items (leaving n/3). Return the minimum number of days to reach 0.
Input
A non-negative integer n.
Output
An integer: the minimum number of days.
Constraints
- 1 <= n <= 2 * 10^9
Examples
Example 1
Input
n = 10
Output
4
10 -> 9 (-1) -> 3 (/3) -> 1 (-... ) ... an optimal path uses 4 days.
Example 2
Input
n = 6
Output
3
6 -> 3 (-... via /2 to 3) -> 1 -> 0, three days.