Program to find the remainder of array elements multiplication divided by n using Python

Introduction

Given an array elements, we have to obtain the remainder after multiplying all the array elements and divide it by n.

find the remainder of array elements multiplication divided by n

Program

def remainder(arr,length,k):
    multi = 1
    for i in range(0,length):
        multi = (multi * (arr[i] % k)) % k
    return multi % k
arr = [101, 1, 5, 2]
length = len(arr)
k = 3
print("Output is ", remainder(arr, length, k))

 

Output

find the remainder of array elements multiplication divided by n Output

Explanation

To obtain the output of the given task, we can follow two approaches: the naive approach or the approach to avoid the overflow.  The naïve approach will give the correct output only if the number is less than 2 ^ 64. Naïve approach is basically multiplying all the elements of the array in the first place and then divide the result by n.

In the above code, we have opted for the second approach: the approach to avoid overflow which is based on distributive property of modular arithmetic. Firstly we take the remainder of number and multiply with the current number. This process will continue until all the array elements are multiplied. And again we take the remainder of resultant multiplication to avoid overflow. Once we get the result we return the remainder.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.