397. Integer Replacement

leetcode medium

#csharp#dynamic-programming#greedy#hash-table#leetcode#math#medium

Task

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8

Output: 3

Explanation: 8 -> 4 -> 2 -> 1

C# solution

matched/original

public class Solution {
    public int IntegerReplacement(int n) {
        Dictionary<long, int> memo = new Dictionary<long, int>();
        return Helper(n, memo);
    }
    
    private int Helper(long n, Dictionary<long, int> memo) {
        if (n == 1) return 0;
        if (memo.ContainsKey(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + Helper(n / 2, memo);
        } else {
            memo[n] = 1 + Math.Min(Helper(n + 1, memo), Helper(n - 1, memo));
        }
        
        return memo[n];
    }
}

C++ solution

auto-draft, review before submit

#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 IntegerReplacement(int n) {
        unordered_map<long, int> memo = new unordered_map<long, int>();
        return Helper(n, memo);
    }
    
    private int Helper(long n, unordered_map<long, int> memo) {
        if (n == 1) return 0;
        if (memo.count(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + Helper(n / 2, memo);
        } else {
            memo[n] = 1 + min(Helper(n + 1, memo), Helper(n - 1, memo));
        }
        
        return memo[n];
    }
}

Java solution

matched/original

class Solution {
    public int integerReplacement(int n) {
        Map<Long, Integer> memo = new HashMap<>();
        return helper(n, memo);
    }
    
    private int helper(long n, Map<Long, Integer> memo) {
        if (n == 1) return 0;
        if (memo.containsKey(n)) return memo.get(n);
        
        if (n % 2 == 0) {
            memo.put(n, 1 + helper(n / 2, memo));
        } else {
            memo.put(n, 1 + Math.min(helper(n + 1, memo), helper(n - 1, memo)));
        }
        
        return memo.get(n);
    }
}

JavaScript solution

matched/original

class Solution {
    integerReplacement(n) {
        const memo = new Map();
        return this.helper(n, memo);
    }
    
    helper(n, memo) {
        if (n === 1) return 0;
        if (memo.has(n)) return memo.get(n);
        
        if (n % 2 === 0) {
            memo.set(n, 1 + this.helper(n / 2, memo));
        } else {
            memo.set(n, 1 + Math.min(this.helper(n + 1, memo), this.helper(n - 1, memo)));
        }
        
        return memo.get(n);
    }
}

Python solution

matched/original

class Solution:
    def integerReplacement(self, n: int) -> int:
        def helper(n, memo):
            if n == 1:
                return 0
            if n in memo:
                return memo[n]
            
            if n % 2 == 0:
                memo[n] = 1 + helper(n // 2, memo)
            else:
                memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
                
            return memo[n]
        
        return helper(n, {})

Go solution

matched/original

func integerReplacement(n int) int {
    memo := make(map[int]int)
    return helper(n, memo)
}

func helper(n int, memo map[int]int) int {
    if n == 1 {
        return 0
    }
    if val, exists := memo[n]; exists {
        return val
    }
    
    if n % 2 == 0 {
        memo[n] = 1 + helper(n/2, memo)
    } else {
        memo[n] = 1 + min(helper(n+1, memo), helper(n-1, memo))
    }
    
    return memo[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Начните с данного числа n и выполните одну из следующих операций:

Если n четное, замените n на n / 2.

Если n нечетное, замените n на n + 1 или n - 1.

Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов.

Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат.

😎