# LeetCode Solution, Medium, 991. Broken Calculator

# [991. Broken Calculator](https://leetcode.com/problems/broken-calculator/)

## 題目敘述

There is a broken calculator that has the integer `startValue` on its display initially. In one operation, you can:

- multiply the number on display by `2`, or
- subtract `1` from the number on display.

Given two integers `startValue` and `target`, return _the minimum number of operations needed to display `target` on the calculator_.

**Example 1:**

    Input: startValue = 2, target = 3
    Output: 2
    Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

**Example 2:**

    Input: startValue = 5, target = 8
    Output: 2
    Explanation: Use decrement and then double {5 -> 4 -> 8}.

**Example 3:**

    Input: startValue = 3, target = 10
    Output: 3
    Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

**Constraints:**

- `1 <= x, y <= 10**9`

### 題目翻譯

題目提供兩個參數 `startValue` 和 `target`。從參數 `startValue` 開始，只能做兩種操作**"減一"**和**"乘2"**，找出最少需要操作幾次次數是可以變成 `target`。

## 解法解析

這題的解法是採用反向的概念，從 `target` 改成**"加 1"**和**"除 2"**。一開始如果是偶數的話就採用 `target /2`，可以盡快的縮小值。如果是奇數的話就 `target - 1`，將其變成偶數。等到 `startValue >= target` 的時候，就可以將之前的操作次數 `ans` 跟 `startValue - target` 相加。因為 `tartget`  跟 `startValue` 之間的差距可以用多個 `+1` 的操作補齊，所以直接 `startValue - target` 即可。

```
startValue = 3, target = 14
1. target = 14 is even => target / 2 => 7, ans = 1
2. target = 7 is odd => target - 1 = 6, ans = 2
3. target = 6 is even => target / 2 = 3, ans = 3
4. startValue >= target => 3(ans) + 3(startValue) - 3(target) => 3
```

### 解法範例

#### Go

```go
func brokenCalc(startValue int, target int) int {
	var ans int
	for target > startValue {
		ans++
		if target%2 == 1 {
			target++
		} else {
			target /= 2
		}
	}
	return ans + startValue - target
}
```

#### JavaScript

```javascript
/**
 * @param {number} startValue
 * @param {number} target
 * @return {number}
 */
var brokenCalc = function (startValue, target) {
    let ans = 0;
    while (target > startValue) {
        ans++;
        if (target % 2) {
            target++;
        } else {
            target /= 2;
        }
    }

    return ans + startValue - target;
};
```

#### Kotlin

```kotlin
class Solution {
    fun brokenCalc(startValue: Int, target: Int): Int {
        var ans = 0
        var diff = target
        while (diff > startValue) {
            ans++
            if (diff % 2 == 1) {
                diff++
            } else {
                diff /= 2
            }
        }
        return ans + startValue - diff
    }
}
```

#### PHP

```php
class Solution
{

    /**
     * @param Integer $startValue
     * @param Integer $target
     * @return Integer
     */
    function brokenCalc($startValue, $target)
    {
        $ans = 0;
        while ($target > $startValue) {
            $ans++;
            if ($target % 2) {
                $target++;
            } else {
                $target /= 2;
            }
        }
        return $ans + $startValue - $target;
    }
}
```

#### Python

```python
class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        ans = 0
        while target > startValue:
            ans += 1
            if target % 2:
                target += 1
            else:
                target = int(target / 2)

        return ans + startValue - target
```

#### Rust

```rust
impl Solution {
    pub fn broken_calc(start_value: i32, target: i32) -> i32 {
        let mut ans = 0;
        let mut diff = target;
        while diff > start_value {
            ans += 1;
            if diff & 1 == 1 {
                diff += 1;
            } else {
                diff /= 2;
            }
        }
        ans + start_value - diff
    }
}
```

#### Swift

```swift
class Solution {
    func brokenCalc(_ startValue: Int, _ target: Int) -> Int {
        var ans = 0
        var diff = target
        while diff > startValue {
            ans += 1
            if diff % 2 == 1 {
                diff += 1
            } else {
                diff /= 2
            }
        }

        return ans + startValue - diff
    }
}
```