leetcode-javascript/solutions/0964-least-operators-to-express-number.js at development · Anuj9826/leetcode-javascript · GitHub

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Least Operators To Express Number
 * Time Complexity: O(log(target))
 * Space Complexity: O(1)
 */
var leastOpsExpressTarget = function (x, target) {
  let baseValue = x;
  let remainingTarget = target;
  let positivePathCost = 0;
  let negativePathCost = 0;
  let finalMinPositive;
  let finalMinNegative;
  let loopExponentLevel = 0;

  for (; ; loopExponentLevel++) {
    let remainderDigit = remainingTarget % baseValue;
    remainingTarget = Math.floor(remainingTarget / baseValue);

    if (loopExponentLevel === 0) {
      positivePathCost = remainderDigit * 2;
      negativePathCost = (baseValue - remainderDigit) * 2;
    } else {
      let costPerTerm = loopExponentLevel;

      let positiveOptionA = remainderDigit * costPerTerm + positivePathCost;
      let positiveOptionB =
        (remainderDigit + 1) * costPerTerm + negativePathCost;
      let newPositivePathCost = Math.min(positiveOptionA, positiveOptionB);

      let negativeOptionA =
        (baseValue - remainderDigit) * costPerTerm + positivePathCost;
      let negativeOptionB =
        (baseValue - remainderDigit - 1) * costPerTerm + negativePathCost;
      let newNegativePathCost = Math.min(negativeOptionA, negativeOptionB);

      positivePathCost = newPositivePathCost;
      negativePathCost = newNegativePathCost;
    }

    finalMinPositive = positivePathCost;
    finalMinNegative = negativePathCost;

    if (remainingTarget === 0) {
      break;
    }
  }

  return Math.min(finalMinPositive, loopExponentLevel + finalMinNegative) - 1;
};