Encuentra el resto de la multiplicación de arreglos 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

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *