Условие

Дан массив position, где position[i] — позиция i-го жетона. За один ход можно:

• Переместить жетон на 2 позиции (бесплатно).

• Переместить жетон на 1 позицию (за 1 единицу стоимости).Нужно найти минимальную стоимость, чтобы все жетоны оказались в одной позиции.

Примеры

Input: [1, 2, 3] Output: 1 Explanation: Первый шаг: переместить жетон с позиции 3 на позицию 1 (стоимость = 0). Второй шаг: переместить жетон с позиции 2 на позицию 1 (стоимость = 1). Общая стоимость — 1.

Input: [2, 2, 2, 3, 3] Output: 2 Explanation: Можно переместить два жетона с позиции 3 на позицию 2. Каждое перемещение стоит 1. Общая стоимость — 2.

Input: [1, 1000000000] Output: 1

Решение

fun minCostToMoveChips(position: IntArray): Int {
    var even = 0
    var odd = 0

    for (pos in position) {
        if (pos % 2 == 0) even++ else odd++
    }

    return minOf(even, odd)
}

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

O(n), где n — длина массива position.

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

O(1), так как используется только два счётчика.