C/C++ program to find remainder of array product divided by n

Array multiplication, we will find the product of all the elements of the given array. Then according to the problem, we will divide the product by the number n. Let us take an example −

Input: arr[] = { 12, 35, 69, 74, 165, 54};
      N = 47
Output: 14

Explanation

The array is as follows {12, 35, 69, 74, 165, 54}, so the product is (12 * 35 * 69 * 74 * 165 * 54) = 19107673200. Now if we want to get the remainder after dividing by 47, the result is 14.

First multiply all the numbers, then take % of n and find the remainder. But in this method, if the number reaches the maximum value of 2^64, it will give wrong answer.

Example

#include <stdio.h>
int main() {
   int arr[] = { 12, 35, 69, 74, 165, 54};
   int len = 6;
   int n = 47 ;
   int mul = 1;
   for (int i = 0; i < len; i++)
      mul = (mul * (arr[i] % n)) % n;
   printf("the remainder is %d", (mul%n));
   return 0;
}

Output

the remainder is 14

The above is the detailed content of C/C++ program to find remainder of array product divided by n. For more information, please follow other related articles on the PHP Chinese website!