Products of ranges in an array

Difficulty Level Hard
Frequently asked in Accolite DE Shaw FreeCharge Google SAP Labs Snapdeal Times Internet
Array Modular Arithmetic Query ProblemViews 2244

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.

Products of ranges in an array

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.

Translate »