🧠 Хитрая задача на Go для продвинутых

Актуально для Go 1.22+

📌 Тень перестановки

У вас есть массив A из n уникальных положительных чисел (`1 ≤ A[i] ≤ 1e6`, `n ≤ 200000`).

Нужно определить, существует ли хотя бы одна перестановка этого массива P, такая что сумма побитовых AND соседних элементов:

P[0]&P[1] + P[1]&P[2] + ... + P[n-2]&P[n-1]

будет чётным числом?

🔍 Наблюдение:

• a & b может быть нечётным только если оба числа нечётные.
• Если в массиве есть двое чётных или двое нечётных, то их можно поставить рядом — и сумма будет чётной.
• Значит, если есть хотя бы две одинаковые по чётности — ответ: YES.

✅ Решение (O(n)):

1. Считаем количество чётных и нечётных чисел.
2. Если хотя бы одно из них ≥ 2 → `"YES"`, иначе — `"NO"`.

💻 **Код на Go:**

```go

func HasEvenAndPermutationSum(A []int) string {
odd, even := 0, 0
for _, v := range A {
if v%2 == 0 {
even++
} else {
odd++
}
}
if even >= 2 || odd >= 2 {
return "YES"
}
return "NO"
}```

🧪 Примеры:

```go
HasEvenAndPermutationSum([]int{5, 2, 8}) // YES
HasEvenAndPermutationSum([]int{1}) // NO
HasEvenAndPermutationSum([]int{3, 7, 11}) // YES
HasEvenAndPermutationSum([]int{2, 4, 6, 8}) // YES
HasEvenAndPermutationSum([]int{3, 2}) // NO```

⚙️ Сложность:

• Время: O(n)
• Память: O(1)

📌 Эта задача проверяет не только знание Go, но и умение думать на уровне битов и арифметических свойств. Отличный пример для собеседования: простая по коду, но требует правильного наблюдения.