Fewest Signs to Reach a Target

Hard

You are given a number base. Build an expression of the form base ? base ? base ? … ? base, where each ? is one of +, -, * or /, whose value equals goal. The usual rules apply: - division is exact, so the result may be a fraction; - there are no parentheses, and multiplication and division happen before addition and subtraction; - there is no unary minus: the expression cannot start with -. For example, with base = 2 the expression 2 * 2 + 2 / 2 equals 5 and uses three signs. Return the smallest number of signs needed to reach goal.

Example 1

base=4, goal=14 → 5

For example, 4 * 4 - 4 / 4 - 4 / 4 = 14 uses five signs, and you cannot do it with fewer.

Example 2

base=7, goal=49 → 1

7 * 7 needs just one sign.

Example 3

base=6, goal=200 → 9

Constraints

2 ≤ base ≤ 100
1 ≤ goal ≤ 2 · 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Memoization Math Dynamic Programming

Similar problems

Thief and Guard Hard Other Orders for the Same Search Tree Hard Mouse, Cat and Cheese Hard Grading the Arithmetic Quiz Hard Grasshopper on an Endless Staircase Hard

Input

base=4, goal=14

Expected

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