Как найти количество пар чисел среди списка, сумма которых кратна 117

Question

Список состоит из 10000 чисел, каждое число не превышает 10000. То, что я пытался, наверняка кардинально не правильно, но вот:

f = open('filename')
a = f.readlines()
a = list(map(int, a))

count = 0
for i in range(len(a) - 1):
    if (a[i] + a[i + 1]) / 117 == range(0, 100):
        count += 1
    print(count)

Answer 1

Кратность можно определить с помощью операции "остаток от деления" %. Получить пары можно с помощью функции zip. print(count) должен вызываться не в цикле а после него.

with open('filename') as f:
    a = [int(line) for line in f]

count = 0
for n1, n2 in zip(a, a[1:]):
    if (n1 + n2) % 117 == 0:
        count += 1
print(count)

Это решение ищет пары соседних чисел, если требовалось найти пары любых чисел нужно использовать itertools.combinations или вложеный цикл.

Answer 2

Для поиска количества пар любых чисел, а не только соседних, использовать вложенные циклы или составлять комбинации неоптимально. Воспользуемся тем свойством, что остаток от деления на Х суммы двух числе равен сумме остатков от деления каждого из этих чисел на Х. Т.е. нам нужно подсчитать количество разных остатков от деления на 117, и перемножить соответствующие пары.

from collections import Counter

f = open(file)
a = f.readlines()
a = list(map(int, a))

a_mod = [i % 117 for i in a] # список остатков от деления на 117

a_mod_dict = Counter(a_mod) # общее количество разных остатков

total = 0
for key in range(1,59): 
    n1 = a_mod_dict[key]
    n2 = a_mod_dict[117-key]
    total += n1*n2

# учитываем числа, которые сами делятся на 117 без остатка
total += (a_mod_dict[0]*(a_mod_dict[0]-1)/2) 

print(total)

БЛОГ НА HUSL

Как найти количество пар чисел среди списка, сумма которых кратна 117

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