wish_me's blog

Count of subarrays whose products don’t have any repeating prime factor
By wish_me, history, 7 years ago, In English

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

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

/deleted message/

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply