Условие
Найди наименьшее положительное целое число
N, для которого выполняются все три условия:1. Цифры
N можно разделить на две группы, сумма которых равна (например: 3213 → `3+2 = 1+3`).2.
N является палиндромом (читается одинаково слева направо и справа налево).3.
N не делится на 10 (исключаем очевидные трюки вроде "1001").Найди такое число, напиши код, который это делает эффективно, и объясни, почему перебор — не самый лучший способ.
Пример:
3213 -> цифры: [3,2,1,3]
Разделение: [3,2] и [1,3] → сумма 5 и 4 → не равны → не подходит
1331 -> [1,3,3,1] → [1,3]=4, [3,1]=4 → ✅ подходит (и палиндром, и сбалансирован)
---
📌 Реализуй функцию:
func FindBalancedPalindrome() int
---
Подсказка:
Задача решается быстрее, если строить палиндромы по шаблону, а не перебирать все числа подряд.
---
🔍 Решение:
```go
package main
import (
"fmt"
"strconv"
)
func isBalanced(digits []int) bool {
n := len(digits)
for i := 1; i < n; i++ {
left := digits[:i]
right := digits[i:]
sumL, sumR := 0, 0
for _, d := range left {
sumL += d
}
for _, d := range right {
sumR += d
}
if sumL == sumR {
return true
}
}
return false
}
func FindBalancedPalindrome() int {
for i := 11; ; i++ {
if i%10 == 0 {
continue
}
s := strconv.Itoa(i)
rev := reverse(s)
if s != rev {
continue
}
digits := make([]int, len(s))
for idx, ch := range s {
digits[idx] = int(ch - '0')
}
if isBalanced(digits) {
return i
}
}
}
func reverse(s string) string {
r := []rune(s)
for i := 0; i < len(r)/2; i++ {
r[i], r[len(r)-1-i] = r[len(r)-1-i], r[i]
}
return string(r)
}
func main() {
fmt.Println("Ответ:", FindBalancedPalindrome())
}
```
✅ Объяснение:
1. Мы перебираем **только палиндромы**, игнорируя шум.
2. Для каждого палиндрома проверяем, можно ли разделить цифры на две группы с равной суммой.
3. Проверка выполняется за `O(n)` на каждое число, где `n` — длина числа.
Такой подход эффективнее полного перебора от 1 до бесконечности.
🔥 Эта задача проверяет:
• знание работы с цифрами и строками
• умение писать генераторы палиндромов
• понимание оптимизации перебора
• грамотное разбиение массива на подмассивы
• работу со строками и рунами в Go