C/C++ Program to Find remainder of array multiplication divided by n
Write a C/C++ program for a given multiple numbers and a number n, the task is to print the remainder after multiplying all the numbers divided by n.
Examples:
Input: arr[] = {100, 10, 5, 25, 35, 14},
n = 11
Output: 9
Explanation: 100 x 10 x 5 x 25 x 35 x 14 = 61250000 % 11 = 9Input : arr[] = {100, 10},
n = 5
Output : 0
Explanation: 100 x 10 = 1000 % 5 = 0
C/C++ Program to Find remainder of array multiplication divided by n using Naive approach:
First multiple all the number then take % by n then find the remainder, But in this approach, if the number is maximum of 2^64 then it give the wrong answer.
Below is the implementation of the above approach:
CPP
// c++ program for the above approach #include <bits/stdc++.h> using namespace std; int findremainder( int arr[], int len, int n) { long long int product = 1; for ( int i = 0; i < len; i++) { product = product * arr[i]; } return product % n; } // Drivers Code int main() { int arr[] = { 100, 10, 5, 25, 35, 14 }; int len = sizeof (arr) / sizeof (arr[0]); int n = 11; cout << findremainder(arr, len, n); return 0; } |
9
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach that avoids overflow :
First take a remainder or individual number like arr[i] % n. Then multiply the remainder with current result. After multiplication, again take remainder to avoid overflow. This works because of distributive properties of modular arithmetic. ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
Below is the implementation of the above approach:
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); } |
9
Time Complexity: O(len), where len is the size of the given array
Auxiliary Space: O(1)
Please refer complete article on Find remainder of array multiplication divided by n for more details!
Contact Us