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 Input : arr[] = {100, 10}, n = 5 Output : 0 100 x 10 = 1000 % 5 = 0
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 una 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
Implementación:
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); }
Java
// Java program to find // remainder when all // array elements are // multiplied. import java.util.*; import java.lang.*; public class GfG{ // Find remainder of arr[0] * arr[1] * // .. * arr[n-1] public static 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 function public static void main(String argc[]) { int[] arr = new int []{ 100, 10, 5, 25, 35, 14 }; int len = 6; int n = 11; // print the remainder of after // multiple all the numbers System.out.println(findremainder(arr, len, n)); } } /* This code is contributed by Sagar Shukla */
Python3
# Python3 program to # find remainder when # all array elements # are multiplied. # Find remainder of arr[0] * arr[1] # * .. * arr[n-1] def findremainder(arr, lens, n): mul = 1 # find the individual # remainder and # multiple with mul. for i in range(lens): mul = (mul * (arr[i] % n)) % n return mul % n # Driven code arr = [ 100, 10, 5, 25, 35, 14 ] lens = len(arr) n = 11 # print the remainder # of after multiple # all the numbers print( findremainder(arr, lens, n)) # This code is contributed by "rishabh_jain".
C#
// C# program to find // remainder when all // array elements are // multiplied. using System; public class GfG{ // Find remainder of arr[0] * arr[1] * // .. * arr[n-1] public static 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 function public static void Main() { int[] arr = new int []{ 100, 10, 5, 25, 35, 14 }; int len = 6; int n = 11; // print the remainder of after // multiple all the numbers Console.WriteLine(findremainder(arr, len, n)); } } /* This code is contributed by vt_m */
PHP
<?php // PHP program to find // remainder when all // array elements are // multiplied. // Find remainder of arr[0] * arr[1] * // .. * arr[n-1] function findremainder($arr, $len, $n) { $mul = 1; // find the individual remainder // and multiple with mul. for ($i = 0; $i < $len; $i++) $mul = ($mul * ($arr[$i] % $n)) % $n; return $mul % $n; } // Driver code $arr = array(100, 10, 5, 25, 35, 14); $len = sizeof($arr); $n = 11; // print the remainder of after // multiple all the numbers echo(findremainder($arr, $len, $n)); // This code is contributed by Ajit. ?>
Javascript
<script> // Javascript program to find // remainder when all // array elements are // multiplied. // Find remainder of arr[0] * arr[1] * // .. * arr[n-1] function findremainder(arr, len, n) { let mul = 1; // find the individual remainder // and multiple with mul. for (let i = 0; i < len; i++) mul = (mul * (arr[i] % n)) % n; return mul % n; } let arr = [ 100, 10, 5, 25, 35, 14 ]; let len = 6; let n = 11; // print the remainder of after // multiple all the numbers document.write(findremainder(arr, len, n)); // This code is contributed by rameshtravel07. </script>
9
Complejidad de tiempo: O(len), donde len es el tamaño de la array dada
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA