Счастливый билет - 2

Question

Решаю задачу . Её суть в том, чтобы определить является ли билет счастливым. Билет счастливый, если число можно разделить на две части, таким образом, чтобы сумма цифр была равная.

Написал код:

n = input()
c = []
for i in list(str(n)):
    c.append(int(i))
a = 0


def sum_num(a):
    while a > 9:
        e = a % 10
        a //= 10
        a += e
    return a



for i in range(0,len(c)):

    e = sum(c[:i])
    e1 = sum(c[i:])

    e = sum_num(e)
    e1 = sum_num(e1)
    if e == e1:
        print('YES')
        a = 1
        break
        
        

if a == 0:
    print('NO')

Но решение проходит только 17 тестов

Answer 1

def chk_lucky(ticket):
    return any(sum(map(int, ticket[i:])) == sum(map(int, ticket[:i])) for i in range(len(ticket)))

Answer 2

x = input()

for i in range(1, len(x)):
    lst0 = list(map(int, x[0:i]))
    lst1 = list(map(int, x[i:len(x)]))
    if sum(lst0) == sum(lst1):
        print('верно')
        print(lst0, lst1)
        exit()
print('неверно')

Answer 3

Вычислим цифровой корень всего числа.

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

def happy(s):
    if len(s) < 2:
        print('NO')
        return
    mod = 0
    for c in s:
        mod = (mod + ord(c) - ord("0")) % 9
    final = mod
    mod = 0
    for c in s:
        mod = (mod + ord(c) - ord("0")) % 9
        if (mod + mod) % 9 == final:
            print('YES')
            return
    print('NO')
    return

happy(input())

Как вариант - можно делать один проход, подсчитывая в списке длиной 10 количество подстрок с соотв. корнем, и в конце для финального корня найти "половинку" c ненулевым счётчиком

mod = 0
mods = [0]*10
for c in s:
    mod = (mod + ord(c) - ord("0")) % 9
    mods[mod] += 1

print('YES') if mods[(mod + 9 * (mod % 2)) // 2] > 0 else print('NO')
return

Answer 4

Интересная задача. Сперва уточню что в задаче Счастливый билет - 2 речь идёт о равенстве цифровых корней (не сумм цифр, как в обычных счастливых билетах) двух половин билета и эти половины не обязаны быть равны.

Например 911 – счастливый билет. Потому что
цифровой_корень(91) = цифровой_корень(1) = 1.

Задача решается за линейное время составлением списков цифровых корней для префиксов билета и для его суффиксов.

Например для строки 8613954720:

цифры	8	6	1	3	9	5	4	7	2	0
цифровые корни префиксов	8	5	6	9	9	5	9	7	9
цифровые корни суффиксов		1	4	3	9	9	4	9	2	0

Если корни соответствующих префикса и суффикса равны, решение найдено. В примере решений три:
8613 954720,
86139 54720,
8613954 720.

def drs(s):
    drs = []
    dr = 0
    for d in map(int, s):
        if dr == 0:
            dr = d
        else:
            s = (dr + d) % 9
            dr = s if s > 0 else 9
        drs.append(dr)
    return drs
 

def main():
    s = input()
    prefixes = drs(s[:-1])
    suffixes = drs(s[:0:-1])[::-1]
    if any(p == s for p, s in zip(prefixes, suffixes)):
        print('YES')
    else:
        print('NO')


main()

P.S. Это решение работает за линейное время и использует линейную память. Интересный вопрос: можно ли решить задачу, располагая только константной памятью?

Да, можно. Второй код в ответе MBo делает почти всё что нужно.

БЛОГ НА HUSL

Счастливый билет - 2

Ответы (4 шт):