Пары с удвоением

Постановка задачи

arr[2 * i + 1] = 2 * arr[2 * i]

arr = [3, 1, 3, 6]

false

arr = [2, 1, 2, 6]

false

arr = [4, -2, 2, -4]

true

Решение

Можно попробовать перебрать все пары чисел и проверить, что одно из них равно удвоенному другому. Таких проверок O(n²), но список подходящих пар еще не даст решения. Каждый элемент можно использовать только один раз, а одно число часто входит сразу в несколько пар. Пары нельзя выбирать независимо: выбор одной блокирует другую, и пришлось бы отдельно искать набор пар на весь массив.

Например, для массива [1, 2, 4, 8] подходят пары (1, 2), (2, 4) и (4, 8). Если взять (2, 4), то 1 и 8 останутся без пары. Подходит только набор (1, 2) и (4, 8). Число таких наборов растет экспоненциально, а по условию длина массива может доходить до 3 * 10⁴. Поэтому такое решение неэффективно, и нужно искать другое.

Идея решения:

Попробуем отсортировать массив по возрастанию и для каждого числа x искать пару 2x. Для быстрой проверки, есть ли в массиве 2x, мы можем хранить частоты элементов в хеш-таблице.

Однако с отрицательными числами возникает проблема: для -2 удвоенное значение равно -4, а -4 стоит левее -2. Если обрабатывать числа по возрастанию, то мы сначала увидим -4 и будем искать -8.

Поэтому будем сортировать по модулю: тогда сначала мы возьмем -2 и будем искать для него -4. Идем по массиву, берем текущее число x. Если частота x равна нулю, то это число уже использовано, пропускаем его. Иначе ищем 2x. Если 2x есть, уменьшаем частоты x и 2x. Если нет, возвращаем false: разбить массив на пары невозможно.

Основные шаги:

1. Считаем частоты всех чисел в arr.
2. Сортируем arr по abs(x) по возрастанию.
3. Идем по числам в этом порядке.
4. Если частота x равна 0, значит, число уже использовано, пропускаем его.
5. Уменьшаем частоту x.
6. Проверяем, есть ли доступное число 2x.
7. Если нет, возвращаем false.
8. Если есть, уменьшаем частоту 2x.
9. Если все числа удалось разложить по парам, возвращаем true.

Рассмотрим пример:

arr = [4, -2, 2, -4]

После сортировки по модулю:

[-2, 2, 4, -4]

Частоты:

-4: 1
-2: 1
 2: 1
 4: 1

Составляем пары:

1. Берем -2, ищем -4. Такое число есть, получаем пару (-2, -4).

2. Берем 2, ищем 4. Такое число есть, получаем пару (2, 4).

3. Остальные элементы уже использованы.

Ответ равен true.

Оценка сложности

Временная сложность

Подсчет частот занимает O(n). Сортировка массива длины n по модулю занимает O(n log n). После этого мы делаем один проход.

Итоговая временная сложность: O(n log n).

Пространственная сложность

Мы храним хеш-таблицу частот, в которой может быть до n разных чисел. Пространственная сложность равна O(n).

Код решения

Приведем код решения.

func canReorderDoubled(arr []int) bool {
    count := map[int]int{}
    for _, num := range arr {
        count[num]++
    }
 
    sort.Slice(arr, func(i, j int) bool {
        return abs(arr[i]) < abs(arr[j])
    })
 
    for _, num := range arr {
        if count[num] == 0 {
            continue
        }
 
        count[num]--
        doubled := num * 2
        if count[doubled] == 0 {
            return false
        }
        count[doubled]--
    }
 
    return true
}
 
func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

Итоги

Задача Array of Doubled Pairs - это пример того, как сортировка задает порядок выбора, а хеш-таблица помогает проверять доступность нужной пары.

1. Суть алгоритма: мы считаем частоты, сортируем числа по абсолютному значению и для каждого еще не использованного x пытаемся найти одно число 2x.
2. Эффективность:
   • Временная сложность: O(n log n), потому что основное время занимает сортировка.
   • Пространственная сложность: O(n), потому что мы храним частоты чисел.
3. Граничные случаи:
   • Отрицательные числа: нужна сортировка по модулю, иначе пары такие как (-2, -4) будут обрабатываться в неправильном порядке.
   • Нули: каждый 0 должен найти второй 0, поэтому нечетное количество нулей приведет к false.
   • Повторы: частоты позволяют не использовать один и тот же элемент в двух разных парах.
4. Оптимальное решение: сначала фиксируем правильный порядок обработки, а затем строим пары. Когда мы идем от меньшего модуля к большему, текущее число уже не может быть удвоением какого-то еще не обработанного меньшего числа.