Find last k digits in product of an array numbers
Last Updated :
01 Aug, 2022
Given a array size of n, find the last k digits (1 <= k < 10) of product of array numbers
Examples:
Input : a[] = {22, 31, 44, 27, 37, 43}
Output : 56
Input : a[] = {24, 7, 144, 77, 29, 19}
Output : 84
A simple solution is to multiply all numbers, then find last k digits of product. This solution may lead overflow as the array product may be high. A better solution is to multiply array elements under modulo of 10k
Implementation:
C++
// 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>
Time Complexity : O(n)
Similar Reads
Computer Science Subjects