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 54Hence 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
subarrayssubsequences, 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