Блог

Учитывая несколько чисел и число n, задача состоит в том, чтобы вывести остаток после умножения всего числа на n.

Примеры:

Input : arr[] = {100, 10, 5, 25, 35, 14}, 
 n = 11
Output : 9
100 x 10 x 5 x 25 x 35 x 14 = 61250000 % 11 = 9

Наивный подход: Сначала умножьте все числа, затем возьмите % на n, затем найдите остаток, но при таком подходе, если число не превышает 2^64, то это дает неправильный ответ.
Подход, позволяющий избежать переполнения : Сначала возьмите остаток или отдельное число, например arr[i] % n. Затем умножьте остаток на текущий результат. После умножения снова возьмите остаток, чтобы избежать переполнения. Это работает из-за распределительных свойств модульной арифметики. ( a * b) % c = ((a % c ) * ( b % c ) ) % c

#to use reduce function import reduce from functools

from functools import reduce

def find_remainder(arr,n):

#use the reduce function to calculate sum

   sum_1=reduce(lambda x,y: x*y,arr)

   remainder=sum_1%n

   print(remainder)

arr=[100,10,5,25,35,14]
n=11
find_remainder(arr,n)

Выход:

9