### wish_me's blog

By wish_me, history, 4 years ago,

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

• -5

 » 4 years ago, # |   +4 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?
•  » » 4 years ago, # ^ |   0 arr length < 1000 and array element < 10**5 then any better approach?
•  » » » 4 years ago, # ^ |   0 Let prev[i] = j denote the largest index j1. A subarray [l,r] is valid if for all x in [l,r], prev[x]
 » 5 weeks ago, # | ← Rev. 2 →   -19 /deleted message/
•  » » 5 weeks ago, # ^ |   +17 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?
•  » » 5 weeks ago, # ^ |   +14 this is problem from live contest on hackerearth ! plz dont discuss until end of the contest
•  » » » 5 weeks ago, # ^ |   0 Ok, will discuss it later!