Programa C/C++ para encontrar el resto de la multiplicación de arrays dividido por n

Dados varios números y un número n, la tarea es imprimir el resto después de multiplicar todo el número dividido por n.

Ejemplos:

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

Enfoque ingenuo: primero multiplique todo el número, luego tome % por n y luego encuentre el resto, pero en este enfoque, si el número es máximo de 2 ^ 64, entonces da la respuesta incorrecta.

Enfoque que evita el desbordamiento: Primero tome un resto o un número individual como arr[i] % n. Luego multiplique el resto con el resultado actual. Después de la multiplicación, vuelva a tomar el resto para evitar el desbordamiento. Esto funciona debido a las propiedades distributivas de la aritmética modular. (un * segundo) % c = ( ( un % c ) * ( segundo % c ) ) % c

// C++ program to find
// remainder when all
// array elements are
// multiplied.
#include <iostream>
using namespace std;
  
// Find remainder of arr[0] * arr[1] *
// .. * arr[n-1]
int findremainder(int arr[], int len, int n)
{
    int mul = 1;
  
    // find the individual remainder
    // and multiple with mul.
    for (int i = 0; i < len; i++)
        mul = (mul * (arr[i] % n)) % n;
  
    return mul % n;
}
  
// Driver code
int main()
{
    int arr[] = { 100, 10, 5, 25, 35, 14 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int n = 11;
  
    // print the remainder of after
    // multiple all the numbers
    cout << findremainder(arr, len, n);
}

9

Consulte el artículo completo sobre Encontrar el resto de la multiplicación de arrays dividido por n para obtener más detalles.