lc964. Least Operators to Express Number

By | June 17, 2019
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

leastOpsExpressTarget(int x, int target)

1. when x > target. min{2 * target – 1, (x – target) * 2}. For example, n = 5, target = 3. First option is 5/5+5/5+5/5. Second option is 5-5/5-5/5. So, formula is

2. needs to calculate the product=x*x*…*x to approach target.

int k = 1;
long product = x;
while (product < target) {
    product *= x;
    k++;
}

3. when product==target, answer is k – 1. For example, n=3, target=27. 3*3*3 has totally 2 operators.

4. when product > target, we need to check if product –  target > target. Because the next round, we should only step in smaller set. Or else there would be circle. For example:

Untitled

in that case, when product > target and product – target > target, resultRight = leastOpsExpressTarget(x, product – target) + k

5. Calculate product / k case. resultLeft = leastOpsExpressTarget(x, product/x) + k – 1

6. result = min{left, right}

least_operator

least_operation