1
$\begingroup$

Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math

For completeness, below is the problem statement and the code. Following the code are the questions I have that would help me understand the solution better.

Problem statement: 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 assuming $x > target$.

Is there a formal proof that the answer is the following:

   min((x-target)*2, (target*2)-1) // target * 2 - 1 for the case where you divide by x initially and add x / x (target - 1) * 2 times
// (x-target) * 2 for the case where you subtract x / x from x (x-target) times.

My issue is that I'm not sure why one of the two sequences of operations described in the comment in the above code is minimal (i.e. why is the answer $min((x-target)*2, (target*2)-1)$). Formally, I think a greedy argument should do the trick. I know that if a multiplication is used, then at least one subtraction operation or division operation has to be used to decrease $x$. Similarly if at least one addition operation is used. So to argue correctness, I would need to argue formally that using any multiplication or addition operation is not minimal. Is the number of operations required necessarily nondecreasing with $x$ (at least when $x > target$)? Subtraction or division operations should decrease $x$, so intuitively if there's a multiplication or an addition operation, it could be deleted along with some other subtraction or division operations, reducing the number of operations.

$\endgroup$
1
  • $\begingroup$ What "if statement body" are you referring to? $\endgroup$
    – D.W.
    Feb 26, 2022 at 3:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.