Given T testcases each testcase consists of an array A[] of length N. Now for each array we have to count the no. of subarrays such that sum of elements of the subarray is divisible by each individual element of the subarray.
Here 1<=T<=100 , 1<=N<=2000 and A[i]<=10^9.
My approach: I am computing the sum and LCM of each subarray and then checking if sum of subarray is divisible by LCM with time complexity of O(TN^2log(n)) but getting TLE. Here log(n) comes from the gcd() function required for computing LCM.Please suggest some optimizations or some other approach for this problem. Thanks in advance.
This can be done in O(n^2).
Use prefix sum array for calculating sum of every subarray and use prefix product array and gcd matrix for every subarray.
Sum for subarray$[i, j]$ can be calculated as sum_{ij} = prefsum[j] - prefsum[i].
Similarly, lcm for subarray$[i, j]$ can be calculated as prod_{ij} = \frac{prod[j]}{prod[i]} where prod[i]!=0 and gcd_{ij} = gcd[i][j] lcm_{ij} = \frac{prod_{ij}}{gcd_{ij}}
Then for every subarray you can calculate the sum in O(1) and lcm in O(1), and then check if is lcm divides the sum.
Ur approach is almost correct,just a few corrections
See since each element <=10^9
Sum <=10^12
so if ur lcm exceeds 10^12 ,there’s no chance that Sum would be divisible
pseudo code:
for i in range(1,n+1):
sum=0,lcm=1
for j in range(i,n+1):
sum=sum+a[j]
lcm=lcm*a[j]/(gcd(lcm,a[j]))
if(lcm is greater than 10^12)
break
if(sum is greater than or equal to lcm):
if(sum%lcm==0)res++
I dont think so gcd should affect that much,if it do tell me,u could use the inbuilt gcd functions(i use them in c++)