Разбор задачи «Сортировка по числу сигналов»

Идея задачи

Для каждого числа важно не только его значение, но и количество единиц в двоичной записи.

Нужно отсортировать массив по двум критериям:

1. сначала по количеству единиц в двоичной записи числа;
2. если количество единиц одинаковое — по возрастанию самого числа.

Именно такой порядок и требуется вывести.

Что значит «количество единиц в двоичной записи»

Рассмотрим несколько чисел:

• 8 = 1000_2 — одна единица;
• 3 = 11_2 — две единицы;
• 9 = 1001_2 — две единицы;
• 7 = 111_2 — три единицы.

Значит, число 8 должно идти раньше чисел 3 и 9, потому что у него меньше единиц в двоичной записи.

Если же сравнивать 3 и 9, то у них одинаковое количество единиц, поэтому раньше идет меньшее число, то есть 3.

Какой порядок сортировки нужен

Для каждого числа x будем смотреть на пару:

• (количество_единиц(x), x)

Тогда сортировка по условию задачи — это просто сортировка по такой паре.

Например, для массива

[10, 100, 3, 7, 8, 9]

получаем:

• 10 -> (2, 10)
• 100 -> (3, 100)
• 3 -> (2, 3)
• 7 -> (3, 7)
• 8 -> (1, 8)
• 9 -> (2, 9)

После сортировки пар получаем порядок:

8, 3, 9, 10, 7, 100

Но нужно внимательно сравнить числа с тремя единицами:

• 7 = 111_2 — 3 единицы
• 100 = 1100100_2 — 3 единицы

При одинаковом количестве единиц раньше идет меньшее число, значит:

8, 3, 9, 10, 7, 100

Это и будет правильный ответ.

Как считать количество единиц

Вариант 1. Готовая функция

Во многих языках уже есть удобные средства:

• в C++: __builtin_popcount(x)
• в Python: bin(x).count('1')

Этого более чем достаточно для данной задачи.

Вариант 2. Ручной подсчет

Можно делить число на 2 и считать остатки, но здесь это не нужно, потому что стандартные средства проще и надежнее.

Алгоритм

1. считываем массив;

2. для сортировки сравниваем числа по двум критериям:

   • сначала по числу единиц в двоичной записи;
   • при равенстве — по самому числу;
3. выводим отсортированный массив.

Почему решение работает

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

Для каждого числа строится ключ сравнения:

• сначала количество единиц;
• затем само число.

Если у одного числа единиц меньше, оно идет раньше. Если единиц поровну, раньше идет меньшее число.

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

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

Пусть в массиве n чисел.

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

Итоговая сложность:

• Время: O(n log n)
• Память: зависит от реализации сортировки, обычно дополнительная память невелика

Решение на C++

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

bool cmp(int a, int b) {
    int ca = __builtin_popcount(a);
    int cb = __builtin_popcount(b);

    if (ca != cb) {
        return ca < cb;
    }
    return a < b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end(), cmp);

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

Пояснение к коду на C++

Функция cmp(a, b) задает правило сравнения двух чисел.

Сначала считаем:

• ca — число единиц в a;
• cb — число единиц в b.

Если ca != cb, то раньше должно идти число с меньшим количеством единиц.

Если ca == cb, то сравниваем сами числа и раньше ставим меньшее.

Затем обычной функцией sort сортируем весь массив по этому правилу.

Решение на Python

def get_key(x):
    return (bin(x).count('1'), x)

n = int(input())
a = list(map(int, input().split()))

a.sort(key=get_key)

print(*a)

Пояснение к коду на Python

Функция get_key(x) возвращает пару:

• количество единиц в двоичной записи числа x;
• само число x.

Именно по таким парам Python и сортирует массив.

Например:

• для 8 ключ будет (1, 8);
• для 3 ключ будет (2, 3);
• для 9 ключ будет (2, 9).

Такой способ полностью совпадает с условием задачи.

Частые ошибки

Ошибка 1. Сортировать только по числу единиц

Если сортировать только по количеству единиц, то при равенстве можно получить неверный порядок.

Например, числа 3 и 9 оба имеют по две единицы, но 3 должно идти раньше 9.

Поэтому нужен второй критерий: само число.

Ошибка 2. Неправильно считать количество единиц

Иногда путают количество единиц с длиной двоичной записи. Это разные вещи.

Например:

• 8 = 1000_2 — длина записи 4, но единица всего одна;
• 7 = 111_2 — длина записи 3, но единиц три.

Ошибка 3. Забыть, что числа могут быть равны

Если в массиве есть одинаковые числа, сортировка должна корректно работать и для них тоже. Наше решение это умеет автоматически.

Небольшой пример вручную

Пусть дан массив:

[5, 2, 7, 8, 3]

Посчитаем количество единиц:

• 5 = 101_2 → 2 единицы
• 2 = 10_2 → 1 единица
• 7 = 111_2 → 3 единицы
• 8 = 1000_2 → 1 единица
• 3 = 11_2 → 2 единицы

Пары получаются такие:

• 5 -> (2, 5)
• 2 -> (1, 2)
• 7 -> (3, 7)
• 8 -> (1, 8)
• 3 -> (2, 3)

Сортируем пары:

• сначала (1, 2), (1, 8)
• потом (2, 3), (2, 5)
• потом (3, 7)

Ответ:

[2, 8, 3, 5, 7]

Вывод

В этой задаче важно заметить, что сортировка идет не по одному признаку, а сразу по двум.

Удобнее всего для каждого числа рассматривать ключ вида:

(количество единиц в двоичной записи, само число)

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