Given an array elements, we have to obtain the remainder after multiplying all the array elements and divide it by n.
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))
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.