Divide by Five or Eleven

Medium

You are given two positive integers start and goal. In one step you may do one of four things to start: - divide it by 5, if it is a multiple of 5; - divide it by 11, if it is a multiple of 11; - subtract 1; - add 1. Return the fewest steps that turn start into goal.

Example 1

start=24, goal=1 → 3

24 → 25 (add 1) → 5 (divide by 5) → 1 (divide by 5 again): three steps.

Example 2

start=3, goal=9 → 6

Dividing does not help here, so just add 1 six times.

Example 3

start=60, goal=1 → 3

60 → 12 (divide by 5) → 11 (subtract 1) → 1 (divide by 11): three steps.

Constraints

1 ≤ start ≤ 10⁴
1 ≤ goal ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Memoization Dynamic Programming

Similar problems

Longest Uphill Walk Hard Clear the Marble Row Hard Six-Cell Tile Slider Hard Uphill-Only Walks Hard Split Into Dictionary Words Medium

Input

start=24, goal=1

Expected

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