Given an array of integers. Find the total number of subarrays whose product of all elements doesn’t contain repeating prime

factor in prime decomposition of resulting number.

Input: 2 3 9

Output: 3

Explanation:

Total sub-array are:-

{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:-

{9} -> {3 * 3}, Since 3 is a repeating prime

factor in prime decomposition of 9

{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime

factor in prime decomposition of 27

{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating

prime factor in prime decomposition of 54

Hence total subarray remains which satisfies our

condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

Try all the subarrays, compute the product directly, find all its prime factors. Works on this two samples perfectly.

In other words: can you provide constraints on the length of array and array elements?

arr length < 1000 and array element < 10**5 then any better approach?

Let prev[i] = j denote the largest index j<i such that gcd(a[j],a[i])>1. A subarray [l,r] is valid if for all x in [l,r], prev[x]<l. Since the length of the array is small here, you can just iterate on every starting point l and try to add indices such that prex[indexes]<l. Works in O(n^2). You can also use RMQ with binary search to find r for each l, that will work in O(nlogn). prev[] array can also be built easily in O(nlog(a[i])) using prime factorisations.

/deleted message/

Try all the

~~subarrays~~subsequences, compute the product directly, find all its prime factors.In other words: can you provide constraints on the length of array and array elements?

this is problem from live contest on hackerearth ! plz dont discuss until end of the contest

Ok, will discuss it later!