Условие

Дан массив целых чисел arr. Отсортируй его по количеству единиц в двоичном представлении каждого числа.

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

Верни отсортированный массив.

Примеры

Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explanation: Количество единиц: [0,1,1,2,1,2,2,3,1]

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explanation: Все числа — степени двойки, у каждого ровно одна единица, поэтому сортируем по значению.

Решение

fun sortByBits(arr: IntArray): IntArray {
    // Подсчёт количества единиц в двоичном представлении числа
    fun countBits(n: Int): Int {
        var count = 0
        var x = n
        while (x > 0) {
            count += x % 2
            x /= 2
        }
        return count
    }

    // Сортировка пузырьком по количеству единиц, затем по значению
    for (i in 0 until arr.size - 1) {
        for (j in 0 until arr.size - i - 1) {
            val c1 = countBits(arr[j])
            val c2 = countBits(arr[j + 1])
            if (c1 > c2 || (c1 == c2 && arr[j] > arr[j + 1])) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }

    return arr
}

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

O(n^2 * log m), где n — длина массива, m — максимальное число (для подсчёта битов).

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

O(1), сортировка выполняется на месте, без доп. памяти.