A Shrinking Pile of Oranges

Hard

There are oranges oranges on the table. Each day you choose exactly one action: - eat one orange; - if the number of remaining oranges x is divisible by 2, eat x / 2 of them; - if x is divisible by 3, eat 2x / 3 of them. Return the fewest days needed to eat all the oranges.

Example 1

oranges=6 → 3

6 is divisible by 3: eat 4, leaving 2. Then eat half, leaving 1. The last orange goes on day three.

Example 2

oranges=11 → 5

Eat one at a time: 11 → 10 → 9, then two thirds: 9 → 3, again: 3 → 1, and the last orange. That is 5 days.

Example 3

oranges=1 → 1

Constraints

1 ≤ oranges ≤ 2 · 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Memoization Dynamic Programming

Similar problems

Every Way to Space the Words Hard Longest Uphill Walk Hard Clear the Marble Row Hard Clearing Colored Cubes Hard Six-Cell Tile Slider Hard

Input

oranges=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 235 tests on the server, hidden ones included.