The problem “Array Queries for multiply, replacements and product” states that you are given an array of integer and there will be three types of queries, where you have to solve the following type of queries:
Type 1: There will be three values left, right and a number X.In this type of query, you have to multiply each element of the array to the value X in the range (left, right) inclusively.
Type 2: It consists of three values left, right as a range. You have to replace the elements in the given range with numbers Y, 2Y, 3Y, and so on.
Type 3: There will be two values left and right as a range. You have to find the product of all the elements within the given range. Since the number can be large. You have to count the total number of trailing zeroes in all the Type3 queries.
Table of Contents
Example
arr[] = {1, 2, 3, 4, 5}
Query: { (3,2,5), (3,4,5), (2,1,3,1), (1,4,5,10), (3,2,4)}3
Explanation
Type3(2, 5), after product of all elements within the range 2 and 5 ⇒ 2 * 3 * 4 * 5 = 120
Type3(3, 5), after product of all elements within the range 3 and 5 ⇒ 3 * 4 * 5 = 60
Type2(1, 3, 1), after replacing each element as y, 2y and 3y and so on in the range 1 to 3
Type1(4, 5, 10), multiply each element with 10 within the range 4 to 5
Type3(2, 4), after the product of all elements within the range 3 and 5 ⇒ 2 * 3 * 40 = 240
Output ⇒ 3, So there will be a total of 3 trailing zeroes we have found in type 3 queries, so it is printed.
Algorithm
- Declare two arrays such that both of the arrays will store the number of trailing zeroes relative to numbers 2 and 5 respectively.
- If we are calling for type1, then get the trailing zeroes of X, in terms of 2 and 5.
- Traverse through the array within a given range. Multiply each number with a value X. Simultaneously, store the value of zeroes as a multiple of 2 and 5 into the array we created for zeroesInTwo and zeroesInFive.
- If we are calling for type2, again get the trailing zeroes of Y, in terms of 2 and 5.
- Store the Y at the first position of the range, 2Y on second and so on. Simultaneously store the count of trailing zeroes to the zeroesInTwo and zeroesInFive.
- And for type3, get the sum of all the values which are in a range in zeroesInTwo and zeroesInFive, and find out the minimum of the count of zeroes in two or count of zeroes in five.
- Print the value in sum.
Explanation
We are given an integer array and three types of queries to solve. One of the queries says that you have to multiply some number within the range. The other one says that you have to replace some numbers. The last one says that you have to find the product of numbers within the range. Then to perform each of the queries we have separately made the three functions which perform their part for each query respectively. Then we will find out the trailing zeroes. For that we have created two arrays one is for in terms of 2, and the other is for in terms of 5.
To solve the first type of query, we will be given a number X and a range in terms of the starting point and an ending point. To find out the trailing zeroes which can be occurred. We will find out if the given number has that trailing zeroes. Then get a count of these trailing zeroes. The same thing is to do with the zeroes in terms of five. We will be traversing the array, from the starting point of the range to the ending point of the range. Then we will be multiplying the value X with each number while traversing. We will also simultaneously perform the addition on the array we create to store zeroes. The same thing is to do in type 2 query, we just need to replace each element by the given number, in a form of series.
To solve the type three query, we will set the value of sumOfTwos and sumOfFives to 0. We will be storing the value in the variable we created sumOfTwos and sumOfFives. Then we will be finding out the minimum of sumOfTwos and sumOfFives. That will be the required and final answer we will be returning.
Code
Implementation in C++ for Array Queries for multiply, replacements and product
#include<vector>
#include<iostream>
using namespace std;
vector<int> zeroesInTwo(1000,0);
vector<int> zeroesInFive(1000,0);
int sum = 0;
int getTwosZeroes(int val)
{
int count = 0;
while (val % 2 == 0 && val != 0)
{
val = val / 2;
count++;
}
return count;
}
int getFivesZeroes(int val)
{
int count = 0;
while (val % 5 == 0 && val != 0)
{
val = val / 5;
count++;
}
return count;
}
void type1(int arr[],int ql, int qr, int x)
{
int twoCount = getTwosZeroes(x);
int fiveCount = getFivesZeroes(x);
for (int i = ql - 1; i < qr; i++)
{
arr[i] = arr[i] * x;
zeroesInTwo[i] += twoCount;
zeroesInFive[i] += fiveCount;
}
}
void type2(int arr[], int ql, int qr, int y)
{
int twoCount = getTwosZeroes(y);
int fiveCount = getFivesZeroes(y);
for (int i = ql - 1; i < qr; i++)
{
arr[i] = (i - ql + 2) * y;
zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
}
}
void type3(int arr[],int ql, int qr)
{
int sumtwos = 0;
int sumfives = 0;
for (int i = ql - 1; i < qr; i++)
{
sumtwos += zeroesInTwo[i];
sumfives += zeroesInFive[i];
}
sum += min(sumtwos, sumfives);
}
int main()
{
int arr[]= {1,2,3,4,5};
int n=sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i < n; i++)
{
zeroesInTwo[i] = getTwosZeroes(arr[i]);
zeroesInFive[i] = getFivesZeroes(arr[i]);
}
type3(arr,2,5);
type3(arr,4,5);
type2(arr,1,3,1);
type1(arr,4,5,10);
type3(arr,2,4);
cout << sum << endl;
return 0;
}
3
Implementation in Java for Array Queries for multiply, replacements and product
import java.util.*;
class type123
{
private static int zeroesInTwo[]=new int[1000];
private static int zeroesInFive[]=new int[1000];
private static int sum = 0;
private static int getTwosZeroes(int val)
{
int count = 0;
while (val % 2 == 0 && val != 0)
{
val = val / 2;
count++;
}
return count;
}
private static int getFivesZeroes(int val)
{
int count = 0;
while (val % 5 == 0 && val != 0)
{
val = val / 5;
count++;
}
return count;
}
private static void type1(int arr[],int ql, int qr, int x)
{
int twoCount = getTwosZeroes(x);
int fiveCount = getFivesZeroes(x);
for (int i = ql - 1; i < qr; i++)
{
arr[i] = arr[i] * x;
zeroesInTwo[i] += twoCount;
zeroesInFive[i] += fiveCount;
}
}
private static void type2(int arr[], int ql, int qr, int y)
{
int twoCount = getTwosZeroes(y);
int fiveCount = getFivesZeroes(y);
for (int i = ql - 1; i < qr; i++)
{
arr[i] = (i - ql + 2) * y;
zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
}
}
private static void type3(int arr[],int ql, int qr)
{
int sumtwos = 0;
int sumfives = 0;
for (int i = ql - 1; i < qr; i++)
{
sumtwos += zeroesInTwo[i];
sumfives += zeroesInFive[i];
}
sum += Math.min(sumtwos, sumfives);
}
public static void main(String []args)
{
int arr[]= {1,2,3,4,5};
int n=arr.length;
Arrays.fill(zeroesInTwo,0);
Arrays.fill(zeroesInFive,0);
for (int i = 0; i < n; i++)
{
zeroesInTwo[i] = getTwosZeroes(arr[i]);
zeroesInFive[i] = getFivesZeroes(arr[i]);
}
type3(arr,2,5);
type3(arr,4,5);
type2(arr,1,3,1);
type1(arr,4,5,10);
type3(arr,2,4);
System.out.println(sum);
}
}
3
Complexity Analysis
Time Complexity
O(n) where “n” is the number of elements in the array. For each query O(N) time is required because we have to traverse whole of the range given to us.
Space Complexity
O(n) where “n” is the number of elements in the array. Since we have created two arrays other than the input, the algorithm has linear space complexity.