Memoization
Math
Dynamic Programming
Description
Given a single positive integer x
, we will write an expression of the form x (op1) x (op2) x (op3) x ...
where each operator op1
, op2
, etc. is either addition, subtraction, multiplication, or division (+
, -
, *
, or /)
. For example, with x = 3
, we might write 3 * 3 / 3 + 3 - 3
which is a value of 3 .
When writing such an expression, we adhere to the following conventions:
The division operator (/
) returns rational numbers.
There are no parentheses placed anywhere.
We use the usual order of operations: multiplication and division happen before addition and subtraction.
It is not allowed to use the unary negation operator (-
). For example, "x - x
" is a valid expression as it only uses subtraction, but "-x + x
" is not because it uses negation.
We would like to write an expression with the least number of operators such that the expression equals the given target
. Return the least number of operators used.
Example 1:
Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3.
The expression contains 5 operations.
Example 2:
Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.
The expression contains 8 operations.
Example 3:
Input: x = 100, target = 100000000
Output: 3
Explanation: 100 * 100 * 100 * 100.
The expression contains 3 operations.
Constraints:
2 <= x <= 100
1 <= target <= 2 * 108
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def leastOpsExpressTarget ( self , x : int , target : int ) -> int :
@cache
def dfs ( v : int ) -> int :
if x >= v :
return min ( v * 2 - 1 , 2 * ( x - v ))
k = 2
while x ** k < v :
k += 1
if x ** k - v < v :
return min ( k + dfs ( x ** k - v ), k - 1 + dfs ( v - x ** ( k - 1 )))
return k - 1 + dfs ( v - x ** ( k - 1 ))
return dfs ( target )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
private int x ;
private Map < Integer , Integer > f = new HashMap <> ();
public int leastOpsExpressTarget ( int x , int target ) {
this . x = x ;
return dfs ( target );
}
private int dfs ( int v ) {
if ( x >= v ) {
return Math . min ( v * 2 - 1 , 2 * ( x - v ));
}
if ( f . containsKey ( v )) {
return f . get ( v );
}
int k = 2 ;
long y = ( long ) x * x ;
while ( y < v ) {
y *= x ;
++ k ;
}
int ans = k - 1 + dfs ( v - ( int ) ( y / x ));
if ( y - v < v ) {
ans = Math . min ( ans , k + dfs (( int ) y - v ));
}
f . put ( v , ans );
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution {
public :
int leastOpsExpressTarget ( int x , int target ) {
unordered_map < int , int > f ;
function < int ( int ) > dfs = [ & ]( int v ) -> int {
if ( x >= v ) {
return min ( v * 2 - 1 , 2 * ( x - v ));
}
if ( f . count ( v )) {
return f [ v ];
}
int k = 2 ;
long long y = x * x ;
while ( y < v ) {
y *= x ;
++ k ;
}
int ans = k - 1 + dfs ( v - y / x );
if ( y - v < v ) {
ans = min ( ans , k + dfs ( y - v ));
}
f [ v ] = ans ;
return ans ;
};
return dfs ( target );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func leastOpsExpressTarget ( x int , target int ) int {
f := map [ int ] int {}
var dfs func ( int ) int
dfs = func ( v int ) int {
if x > v {
return min ( v * 2 - 1 , 2 * ( x - v ))
}
if val , ok := f [ v ]; ok {
return val
}
k := 2
y := x * x
for y < v {
y *= x
k ++
}
ans := k - 1 + dfs ( v - y / x )
if y - v < v {
ans = min ( ans , k + dfs ( y - v ))
}
f [ v ] = ans
return ans
}
return dfs ( target )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 function leastOpsExpressTarget ( x : number , target : number ) : number {
const f : Map < number , number > = new Map ();
const dfs = ( v : number ) : number => {
if ( x > v ) {
return Math . min ( v * 2 - 1 , 2 * ( x - v ));
}
if ( f . has ( v )) {
return f . get ( v ) ! ;
}
let k = 2 ;
let y = x * x ;
while ( y < v ) {
y *= x ;
++ k ;
}
let ans = k - 1 + dfs ( v - Math . floor ( y / x ));
if ( y - v < v ) {
ans = Math . min ( ans , k + dfs ( y - v ));
}
f . set ( v , ans );
return ans ;
};
return dfs ( target );
}
GitHub