991. Broken Calculator

LeetCode medium оригинал: C# #backtracking #csharp #leetcode #medium

LeetCode Static

Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:

Умножить число на экране на 2, или

Вычесть 1 из числа на экране.

Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример

Input: startValue = 2, target = 3

Output: 2

Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

C# решение

сопоставлено/оригинал

public class Solution {
    public int BrokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int BrokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

Java решение

сопоставлено/оригинал

public class Solution {
    public int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}

JavaScript решение

сопоставлено/оригинал

var brokenCalc = function(startValue, target) {
    let operations = 0;
    
    while (target > startValue) {
        operations++;
        if (target % 2 === 0) {
            target /= 2;
        } else {
            target += 1;
        }
    }
    
    return operations + (startValue - target);
};

Python решение

сопоставлено/оригинал

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

Go решение

сопоставлено/оригинал

func brokenCalc(startValue int, target int) int {
    operations := 0
    
    for target > startValue {
        operations++
        if target % 2 == 0 {
            target /= 2
        } else {
            target++
        }
    }
    
    return operations + (startValue - target)
}

Algorithm

Обратный путь:

Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.

Если target четный, разделите его на 2, иначе прибавьте 1.

Подсчет операций:

Повторяйте шаги, пока target не станет меньше или равен startValue.

После этого вычитайте из startValue оставшееся значение target.

Возврат результата:

Возвращайте суммарное количество выполненных операций.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.