Anybody please explain the question. I wrote code but it fails the testcases and passes the base cases.
this is my code. I think i misunderstood the question. please explain me the question. thanks in advance.
#include <stdio.h>
long int mult(int arr[],long int l,long int r,long int m);
int main(void) {
// your code goes here
long int n,t,l,r,m;
scanf("%ld",&n);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
scanf("%ld",&t);
while(t--){
scanf("%ld%ld%ld",&l,&r,&m);
long int ans= mult(arr,l,r,m);
printf("%ld\n",ans);
}
return 0;
}
long int mult(int arr[],long int l,long int r,long int m)
{
long int res=1;
for(long int i=l-1;i<r;i++){
res=res*arr[i];
}
return res%m;
}
Question : Given the start and end indices of an array , you have to output the product of all numbers in this range (modulo M).
Solution : What you are doing is correct but it’ll give TLE. To solve the problem efficiently you have to store the product of all elements upto index i in another array. Now when you are given a query you just have to take product of all elements upto r divided by product of elements till l-1 , modulo M.
Give it a try !
1 Like
Sorry I didn’t get your answer.
Do i need to do like this?
for(long int i=l-1;i<r;i++){
res[i]=res[i]*arr[i];
}
return res[i]%m;
Suppose your array is
1 2 4 6 3 4 5
and query is l=1 r=7 m=10
Your solution multiplies elements from 1 to 7 which takes O(n) time and you are doing this t times so overall complexity of your algorithm if O(txn) [You are performing txn iterations] which is not feasible in this question.
So you have to reduce the complexity of your algorithm.
P.S. If you don’t understand complexity and big-O notation just do a simple google search
If array can contain zeroes as well , then this approach gives runtime error.
Yeah right , but
1<=a[i]<=100 , that’s the range given in the question.
1 Like
okay @rishav. I have just checked few solutions but many people took prime numbers in array and did repeated squaring some other stuff… but i dont understand why they did like that and could you please give me a hint how to reduce for my solution.
Thank you very much.
Oh okay. I didn’t read the que…
That is actually another approach to solve the problem. You can prime factorize each number into its prime factors. Now when you’re give a query you simply have to add up the powers of prime numbers present in the range of numbers. This is actually a better solution.
The earlier solution may give error because the product of numbers can be quite large and would not fit in the built-in datatypes.
You can refer to the editorial CHMOD - Editorial
ok thank you @rishav_iitkgp.
I have used your approach and written in python since python has no limit on integers.
even if all the elements in the array are 100 then product would be 100^(100000) since N limit is 100,000 . 100^(100000) can be done in python.
but still I’m getting Time limit exceeded .
could you please tell why TLE?
That is because the complexity of your algorithm is O(queries*n). How?
In the worst case , queries = 10^5 and in every query you are given the ends of the array i.e 1 , n.
So the total number of iterations becomes 10^5 * 10^5 in worst case.
Such large number of iterations takes a lot of time , that’s why TLE.
The algorithm given in the editorial takes 25 * 10^5 iterations .
@rishav_iitkgp , what would your opinion be for using a segment tree.
Here is my code for refn :- CodeChef: Practical coding for everyone
yet WA.