You are given a list of positive integers called nums. A contiguous subarray is considered special when the product of all its elements has an odd number of positive divisors.
Return the total number of special subarrays in nums.
A positive integer has an odd number of positive divisors if and only if it is a perfect square. Therefore, a subarray is special exactly when the product of its elements is a perfect square.
Method Signature
long countSpecialSubarrays(List<Integer> nums)
nums contains the positive integers in the given list.- The method returns the number of contiguous subarrays whose element product has an odd number of positive divisors.
- A subarray must contain at least one element.
Constraints
1 ≤ nums.size() ≤ 100,0001 ≤ nums.get(i) ≤ 1,000,000,000- Every value in
nums is a positive integer.
- The answer fits in a signed 64-bit integer.
Examples
Example 1
countSpecialSubarrays(nums = [2, 8, 3, 12])
Output: 3
The special subarrays are [2, 8], [3, 12], and [2, 8, 3, 12]. Their products are 16, 36, and 576, which are perfect squares.
Example 2
countSpecialSubarrays(nums = [1, 4, 2, 18])
Output: 6
The six special subarrays are [1], [4], [1, 4], [2, 18], [4, 2, 18], and [1, 4, 2, 18]. Their products are 1, 4, 4, 36, 144, and 144, respectively. Each product is a perfect square.
Example 3
countSpecialSubarrays(nums = [2, 3, 5])
Output: 0
No contiguous subarray has a product that is a perfect square.
Example 4
countSpecialSubarrays(nums = [9])
Output: 1
The only subarray has product 9, which has an odd number of positive divisors.