Encuentra los últimos k dígitos en el producto de una array de números

Dado un tamaño de array de n, encuentre los últimos k dígitos (1 <= k < 10) del producto de números de array 

Ejemplos: 

Input  : a[] = {22, 31, 44, 27, 37, 43}
Output : 56

Input  : a[] = {24, 7, 144, 77, 29, 19}
Output : 84

Una solución simple es multiplicar todos los números y luego encontrar los últimos k dígitos del producto. Esta solución puede provocar un desbordamiento ya que el producto de la array puede ser alto.

Una mejor solución es multiplicar los elementos de la array con un módulo de 10 ^k 

// CPP program to find the last k digits in
// product of array
#include <bits/stdc++.h>
using namespace std;
 
// Returns last k digits in product of a[]
int lastKDigits(int a[], int n, int k)
{
    int num = (int)pow(10, k);
 
    // Multiplying array elements under
    // modulo 10^k.
    int mul = a[0] % num;
    for (int i = 1; i < n; i++) {
        a[i] = a[i] % num;
        mul = (a[i] * mul) % num;
    }
    return mul;
}
 
// Driven program
int main()
{
    int a[] = { 22, 31, 44, 27, 37, 43 };
    int k = 2;
    int n = sizeof(a) / sizeof(a[0]);
    cout << lastKDigits(a, n, k);
    return 0;
}

// Java program to find
// the last k digits in
// product of array
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Returns last k digits in product of a[]
    static int lastKDigits(int a[], int n, int k)
    {
        int num = (int)(Math.pow(10, k));
     
        // Multiplying array elements
        // under modulo 10^k.
        int mul = a[0] % num;
         
        for (int i = 1; i < n; i++) {
            a[i] = a[i] % num;
            mul = (a[i] * mul) % num;
        }
        return mul;
    }
     
// Driven program
public static void main(String args[])
{
    int a[] = { 22, 31, 44, 27, 37, 43 };
    int k = 2;
    int n = a.length;
     
    System.out.println(lastKDigits(a, n, k));
}
 
}
 
 
/*This code is contributed by Nikita Tiwari.*/

# Python 3 program to find the last
# k digits inproduct of array
import math
 
# Returns last k digits
# in product of a[]
def lastKDigits(a, n, k) :
     
    num = (int)(math.pow(10, k))
     
    # Multiplying array elements
    # under modulo 10^k.
    mul = a[0] % num
     
    for i in range(1,n) :
        a[i] = a[i] % num
        mul = (a[i] * mul) % num
     
    return mul
     
 
# Driven program
a = [ 22, 31, 44, 27, 37, 43 ]
k = 2
n = len(a)
print(lastKDigits(a, n, k))
 
 
# This code is contributed by Nikita Tiwari.

// C# program to find
// the last k digits in
// product of array
using System;
 
class GFG {
     
    // Returns last k digits in product of a[]
    static int lastKDigits(int []a, int n, int k)
    {
        int num = (int)(Math.Pow(10, k));
     
        // Multiplying array elements
        // under modulo 10^k.
        int mul = a[0] % num;
         
        for (int i = 1; i < n; i++) {
            a[i] = a[i] % num;
            mul = (a[i] * mul) % num;
        }
        return mul;
    }
     
    // Driven program
    public static void Main()
    {
        int []a = { 22, 31, 44, 27, 37, 43 };
        int k = 2;
        int n = a.Length;
         
        Console.WriteLine(lastKDigits(a, n, k));
    }
 
}
 
 
// This code is contributed by vt_m.

<?php
// PHP program to find
// the last k digits in
// product of array
 
// Returns last k digits
// in product of a[]
function lastKDigits($a, $n, $k)
{
     
    $num = (int)pow(10, $k);
 
    // Multiplying array elements
    // under modulo 10^k.
    $mul = $a[0] % $num;
    for ($i = 1; $i < $n; $i++)
    {
        $a[$i] = $a[$i] % $num;
        $mul = ($a[$i] * $mul) % $num;
    }
    return $mul;
}
 
// Driver Code
$a = array( 22, 31, 44, 27, 37, 43 );
$k = 2;
$n = sizeof($a);
echo(lastKDigits($a, $n, $k));
 
// This code is contributed by Ajit.
?>

<script>
 
// Javascript program to find
// the last k digits in
// product of array
 
// Returns last k digits in product of a[]
function lastKDigits(a, n, k)
{
    let num = (Math.pow(10, k));
   
    // Multiplying array elements
    // under modulo 10^k.
    let mul = a[0] % num;
       
    for(let i = 1; i < n; i++)
    {
        a[i] = a[i] % num;
        mul = (a[i] * mul) % num;
    }
    return mul;
}
 
// Driver code
let a = [ 22, 31, 44, 27, 37, 43 ];
let k = 2;
let n = a.length;
 
document.write(lastKDigits(a, n, k));
 
// This code is contributed by suresh07 
 
</script>

Producción: 

 56

Complejidad de tiempo : O(n)