21 · АРИФМЕТИКА

Математика

Остаток, НОД и аккуратная работа с переполнением покрывают большинство математических задач.

3 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Остаток

digit := n % 10
n /= 10

Остаток отрицательного числа в Go тоже отрицательный.

Большие числа

var total int64
total += int64(value)

Переходи к int64 до умножения, а не после.

НОД

for b != 0 { a, b = b, a%b }

Алгоритм Евклида работает за O(log min(a,b)).

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Быстрое возведение в степень

На каждом шаге делим степень пополам.

O(log n) time · O(1) space

solution.go

func myPow(x float64, n int) float64 {
    power := int64(n)
    if power < 0 { x, power = 1/x, -power }
    answer := 1.0
    for power > 0 {
        if power&1 == 1 { answer *= x }
        x *= x
        power >>= 1
    }
    return answer
}

ПРИМЕР РЕШЕНИЯ

Количество простых

Решето отмечает кратные.

O(n log log n) time · O(n) space

solution.go

func countPrimes(n int) int {
    composite, count := make([]bool, n), 0
    for p := 2; p < n; p++ {
        if composite[p] { continue }
        count++
        if p <= (n-1)/p {
            for multiple := p*p; multiple < n; multiple += p { composite[multiple] = true }
        }
    }
    return count
}

ПРИМЕР РЕШЕНИЯ

Палиндром-число

Строим только обратную половину числа, избегая переполнения.

O(log n) time · O(1) space

solution.go

func isPalindromeNumber(x int) bool {
    if x < 0 || x%10 == 0 && x != 0 { return false }
    reversed := 0
    for x > reversed {
        reversed = reversed*10 + x%10
        x /= 10
    }
    return x == reversed || x == reversed/10
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Возможное переполнение
Поведение отрицательного остатка
Особые значения 0 и 1