Задачи по алгоритмам: ищем непростые числа / Habr

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

Наконец, все работает. Остаются черновики, которые выбросить жалко. Выброшу лишнее с черновика и оставлю конспект, который и через годы напомнит решение.

Говорят "У человека феноменальная память - он помнит все". Он записывает. Не помните, что делали три дня назад? Ведите дневник, а не покупайте "таблетки для памяти".

Задача

Дан массив положительных целых чисел. Сделать так, чтобы каждые два соседних числа оказались взаимно просты. Заменить два соседних числа a и b на наименьшее общее кратное lcm(a, b), когда a и b- взаимно не просты.

Два числа a и b взаимно просты, когда наибольший общий делитель чисел gcd(a, b) равен 1.

Наибольший общий делитель

b - делитель a, когда a делится на b. Пример: 6 делится на 6, 3, 2 и 1, поэтому 6, 3, 2 и 1 - делители 6.

c - общий делитель чисел a и b, когда a делится на c и b делится на c.

Примеры:

12 = 6 * 2 = 3 * 4 = 3 * 2 * 2
18 = 9 * 2 = 3 * 3 * 2
45 = 9 * 5 = 3 * 3 * 5

3 - общий делитель чисел 18, 45.
9 - общий и наибольший делитель чисел 18, 45.
3 - общий и наибольший делитель чисел 12, 18, 45.

Часто говорят "множители числа" вместо "делители".

Поиск наибольшего общего делителя: разложение числа на множители

Разложить число a на множители значит подобрать делители числа a и записать

Число p - простое, когда p делится только на 1 и p.

Разложить число a на простые множители значит записать

$a = p_1^{b_1} * p_2^{b_2} * ... * p_n^{b_n}$

где - простые числа, а степени - положительные целые. При этом $p_1 \not= p_2 \not= p_n$ - простые числа не повторяются.

Найдем наибольший общий делитель чисел a и b, когда разложим числа на простые множители.

Поиск наибольшего общего делителя: алгоритм Евклида

Большие числа раскладывать на множители утомительно. Алгоритм Евклида поможет найти наибольший общий делитель проще.

            | a, когда b = 0
gcd(a, b) = |
            | gcd(b, a mod b), когда b != 0

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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

Наименьшее общее кратное

Наименьшее общее кратное чисел a и b - наименьшее целое число c, которое делится на a и делится на b. Обозначают lcm(a, b).

${lcm(a, b)} = {a * b \over gcd(a, b)}$

Решение задачи

Движемся по массиву слева направо, ищем два смежных числа, которые взаимно не просты - 1 < gcd(c, d).

Пусть в массиве [a, b, c, d, e, f] взаимно просты a, b и взаимно просты b, c, а c, d - нет. Заменим числа c и d на c1 = lcm(c, d). Теперь придется снова проверить взаимную простоту c1 и b. Продолжим движение вправо, но запомним, что должны сходить влево. Заменяем числа nums[i], nums[i + 1], пока они взаимно не просты.

Теперь сходим влево - заменяем числа nums[i - 1], nums[i], пока они взаимно не просты.

Порядок замен не важен - это можно доказать.

Теперь проверим числа nums[i], nums[i + 1] снова, если заменили nums[i - 1], nums[i] хотя бы раз. Повторяем замены вправо и влево, чтобы nums[i] оказался взаимно прост с обоими соседями - слева nums[i - 1] и справа nums[i + 1].

Объединяем смежные числа, которые взаимно не просты с nums[i]

Затем переходим к следующему числу i = i + 1 и снова объединяем с непростыми соседями. Продолжаем, пока не дойдем до конца массива.

Код на C++

Напишем и проверим код на leetcode.com.

Задача предлагает массив vector<int> nums, но мы хотим удалять числа посреди массива, а vector справляется с этим плохо, потому что хранит числа в памяти непрерывно. Вот так работает метод vector::erase():

Способ 1 - запросить новый блок памяти, копировать элементы, кроме удаленного:
Способ 2 - сдвинуть элементы после удаленного влево на один:

Превратим массив в двусвязный список - он удаляет элементы из середины быстрее.

using NumsList = list<int>;
using NumsVector = vector<int>;
NumsVector replaceNonCoprimes(NumsVector &vec) {
    NumsList nums{vec.begin(), vec.end()};
    // ...
}

Теперь шагаем по списку слева направо: берем следующее число и объединяем с "непростыми" соседями справа и слева. Функция mergeRight объединяет число с соседом справа, а mergeLeft - слева.

NumsVector replaceNonCoprimes(NumsVector &vec) {
    // ...
    auto iter = nums.begin(); 
    while (nums.end() != iter) {
        bool replaced = mergeRight(nums, iter);
        if (replaced) {
            do { replaced = mergeRight(nums, iter); }
            while(replaced);
            do { replaced = mergeLeft(nums, iter); }
            while(replaced);
        } else { 
            ++iter; 
        }
    }
    //...
}

Затем копируем числа из списка в массив и возвращаем:

using NumsList = list<int>;
using NumsVector = vector<int>;
NumsVector replaceNonCoprimes(NumsVector &vec) {
    // ...
    vec = {nums.begin(), nums.end()};
    return vec;
}

Отправляем на проверку - программа работает.

LeetCode говорит, что программа жрет больше времени и памяти, чем другие.

Простой, но медленный и прожорливый код

using NumsList = list<int>;
bool nonCoprimes(int a, int b) {
    return 1 < std::gcd(a, b);
}

bool mergeRight(NumsList &nums, NumsList::iterator &iter) {
    bool merged = false;
    if (!nums.empty() && nums.end() != iter) {
        auto right = next(iter);
        if (nums.end() != right && nonCoprimes(*iter, *right)) {
            *iter = std::lcm(*iter, *right);
            nums.erase(right);
            merged = true;
        }
    }

    return merged;
}

bool mergeLeft(NumsList &nums, NumsList::iterator &iter) {
    bool merged = false;
    if (!nums.empty() && nums.end() != iter && nums.begin() != iter) {
        auto left = prev(iter);
        if (nonCoprimes(*left, *iter)) {
            *iter = std::lcm(*left, *iter);
            nums.erase(left);
            merged = true;
        }
    }

    return merged;
}

vector<int> replaceNonCoprimes(vector<int>& vec) {
    NumsList nums{vec.begin(), vec.end()};
    auto iter = nums.begin(); 
    while (nums.end() != iter) {
        bool replaced = mergeRight(nums, iter);
        if (replaced) {
            do { replaced = mergeRight(nums, iter); }
            while(replaced);
            do { replaced = mergeLeft(nums, iter); }
            while(replaced);
        } else { 
            ++iter; 
        }
    }
    vec = {nums.begin(), nums.end()};

    return vec;
}

Оптимизация

Интуиция подсказывает - программа расходует память, когда копирует числа из вектора в список. Научим программу работать с вектором.

Не удаляем элементы массива, но стираем - пишем 0. Так мы не используем метод vector::erase(), но теперь массив содержит нули между соседними числами.

Запомним части массива, которые разбиваем - пусть mergeLeft знает, где ближайший сосед слева. Так не придется ходить по массиву и искать соседние числа среди нулей.

Индекс right подскажет функции mergeRight, где ближайший сосед справа. Массив не содержит нулей правее right - туда программа еще не добралась.

mergeLeft запоминает новую часть массива

mergeLeft забывает часть массива, когда в части не осталось чисел

Программа запоминает новую часть массива, когда переходит к следующему числу

Уберем нули из массива, прежде чем отдать массив на проверку. Два способа:

Копируем числа в новый массив, кроме нулей

NumsVector result;
for (const auto &n: nums) {
    if (0 < n) {
        result.push_back(n);
    }
}

Пусть программа знает, сколько чисел стерла, тогда знает, сколько памяти нужно:

NumsVector result{nums.size() - merged_count};
int w = 0;
for (const auto &n: nums) {
    if (0 < n) {
        result[w++] = n;
    }
}

Сожмем исходный массив так, что нули окажутся в хвосте, а хвост отстрижем

int w = 0;
for (int r = 0; r < nums.size(); ++r) {
    if (0 < nums[r]) {
        nums[w++] = nums[r];
    }
}
nums.resize(w);

Экономим еще немного памяти, если используем vector вместо stack:

using SlicesStack = vector<int>;

Скромный и неприхотливый код

using NumsVector = vector<int>;
using SlicesStack = vector<int>;
NumsVector replaceNonCoprimes(NumsVector &nums) {
    int merged_count = 0;
    int i = 0;
    SlicesStack slices;
    int right = i + 1;
    while (i < nums.size() && right < nums.size()) {
        bool merged = mergeRight(nums, i, right, merged_count);
        if (merged) {
            mergeLeft(nums, i, slices, merged_count);
        } else {
            if (1 < right - i) {
                slices.push_back(i);
            }
            i = right;
            right = i + 1;
            }
    }

    if (0 < merged_count) {
        int w = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (0 < nums[r]) {
                nums[w++] = nums[r];
            }
        }
        nums.resize(nums.size() - merged_count);
    }

    return nums;
}

bool coprimes(int a, int b) {
    return 1 == std::gcd(a, b);
}

bool mergeRight(NumsVector &nums, int i, int &right, int &merged_count) {
    bool merged = false;
    while (right < nums.size() && !coprimes(nums[i], nums[right])) {
        nums[i] = std::lcm(nums[i], nums[right]);
        nums[right] = 0;
        ++right;
        merged = true;
        ++merged_count;
    }

    return merged;
}

void mergeLeft(NumsVector &nums, int i, SlicesStack &slices, int &merged_count) {
    int p = i - 1;
    while (0 <= p) {
        if (0 == nums[p]) {
            if (slices.empty()) { return; }
            p = slices.back();
        }
        if (!coprimes(nums[p], nums[i])) {
            if (i - 1 == p) {
                slices.push_back(p);
            }
            nums[i] = std::lcm(nums[p], nums[i]);
            nums[p] = 0;
            ++merged_count;
            p = --slices.back();
            if (p < 0 || 0 <= p && 0 == nums[p]) {
                slices.pop_back();
                p = !slices.empty() ? slices.back() : -1;
            }
        } else { break; }
    }
}

Пишите в комментариях, как бы вы еще сэкономили память или ускорили код, или предлагайте другие решения.