Table of Contents
Problem Statement
The problem “Products of ranges in an array” states that you are given an integer array consisting of numbers range from 1 to n and q number of queries. Each query contains the range. The problem statement asks to find out the product within the given range under modulo M where m is any prime number.
Example
arr[] = {1,2,3,4,5,6}
M = 131
Query = [1, 6], [2, 4]65 24
Explanation
From 1 to 6, the product of the range is 720 when modulo is applied it leaves 65 and 24 remains the same.
Approach
Given a range of a number as a starting number and an ending number. Considering this range as it is filled with all of the in-between numbers. Our task is to find out the product of numbers numbers within this range. We will be calculating the product and the inverse product, then, later on, we will be solving the query, with this, two steps of calculating pre-product and inverse product, we will be solving multiple queries at a time, we don’t need to go through the whole algorithm to solve a query.
First, calculate the pre-product of the array, that is, we have to traverse the array and first of all, we need to copy the given array’s first element to the pre-product array’s first element. We will traverse the array, from the first position of the given array, and store the product of the previous element of the given array and the product array, in order to maintain the modulo, we will be storing the modulo of the product we get and store it to the product array.
In the next step, we will be calculating the inverse product, with this, we mean the inverse product of the range, such that if we calculating the inverse product till the ith index, the inverse product will be the product of the all the numbers from the range 0 to i. With this, we can solve the query in constant time. We don’t need to make extra efforts for solving each query. Now if we get the query to solve we just return the product of PreProduct[right] and PreInverseProduct[left-1]. This will be the required answer.
Code
C++ code to find Products of ranges in an array
#include <iostream>
using namespace std;
#define MAX 100
int PreProductArray[MAX];
int PreInverseProduct[MAX];
int InverseP(int a, int modulo)
{
int mP = modulo, temp, quotient;
int xP = 0, x = 1;
if (modulo == 1)
return 0;
while (a > 1)
{
quotient = a / modulo;
temp = modulo;
modulo = a % modulo;
a = temp;
temp = xP;
xP = x - quotient * xP;
x = temp;
}
if (x < 0)
x += mP;
return x;
}
void calculatePreProduct(int A[], int N, int P)
{
PreProductArray[0] = A[0];
for (int i = 1; i < N; i++)
{
PreProductArray[i] = PreProductArray[i - 1] *A[i];
PreProductArray[i] = PreProductArray[i] % P;
}
}
void calculatePreInverseProduct(int A[], int N, int P)
{
PreInverseProduct[0] = InverseP(PreProductArray[0], P);
for (int i = 1; i < N; i++)
PreInverseProduct[i] = InverseP(PreProductArray[i], P);
}
int calculateProduct(int A[], int L, int R, int P)
{
L = L - 1;
R = R - 1;
int ans;
if (L == 0)
ans = PreProductArray[R];
else
ans = PreProductArray[R] *
PreInverseProduct[L - 1];
return ans;
}
int main()
{
int Arr[] = { 1, 2, 3, 4, 5, 6 };
int N = sizeof(Arr) / sizeof(Arr[0]);
int Modulo = 131;
calculatePreProduct(Arr, N, Modulo);
calculatePreInverseProduct(Arr, N, Modulo);
int Left = 1, Right = 6;
cout << calculateProduct(Arr, Left, Right, Modulo) << endl;
Left = 2, Right = 4;
cout << calculateProduct(Arr, Left, Right, Modulo)
<< endl;
return 0;
}
65 24
Java code to find Products of ranges in an array
class ProductInRange
{
static int MAX = 100;
static int PreProductArray[] = new int[MAX];
static int PreInverseProduct[] = new int[MAX];
static int InverseP(int a, int modulo)
{
int mP = modulo, temp, quotient;
int xP = 0, x = 1;
if (modulo == 1)
return 0;
while (a > 1)
{
quotient = a / modulo;
temp = modulo;
modulo = a % modulo;
a = temp;
temp = xP;
xP = x - quotient * xP;
x = temp;
}
if (x < 0)
x += mP;
return x;
}
static void calculatePreProduct(int A[], int N, int P)
{
PreProductArray[0] = A[0];
for (int i = 1; i < N; i++)
{
PreProductArray[i] = PreProductArray[i - 1] *
A[i];
PreProductArray[i] = PreProductArray[i] % P;
}
}
static void calculatePreInverseProduct(int A[], int N, int P)
{
PreInverseProduct[0] = InverseP(PreProductArray[0], P);
for (int i = 1; i < N; i++)
PreInverseProduct[i] = InverseP(PreProductArray[i],
P);
}
static int calculateProduct(int A[], int L, int R, int P)
{
L = L - 1;
R = R - 1;
int ans;
if (L == 0)
ans = PreProductArray[R];
else
ans = PreProductArray[R] *
PreInverseProduct[L - 1];
return ans;
}
public static void main(String[] args)
{
int Arr[] = { 1, 2, 3, 4, 5, 6 };
int Modulo = 131;
calculatePreProduct(Arr, Arr.length, Modulo);
calculatePreInverseProduct(Arr, Arr.length,
Modulo);
int Left = 1, Right = 6;
System.out.println(calculateProduct(Arr, Left,
Right, Modulo));
Left = 2;
Right = 4;
System.out.println(calculateProduct(Arr, Left,
Right, Modulo));
}
}
65 24
Complexity Analysis
Time Complexity
O(N log M+Q), here log M is because of finding the inverse for product. And then O(Q) for answering queries.
Space Complexity
O(N) where “N” is the number of elements in the array. Because we stored preProduct and preProductInverse arrays.