Count Subarrays by Divisor Sum

Given an array, count the number of subarrays whose sum of divisor counts of elements is odd.

Asked in the Online assessment stage. Coding round, 3 questions in 1h30.

Implement count_odd_divisor_sum_subarrays(nums). The input is an array of positive integers. For each element, determine its number of positive divisors. Return the number of contiguous subarrays whose divisor counts sum to an odd number.

Examples

• nums = [1, 2, 4] returns 4. Their divisor-count parities are [1, 0, 1].
• nums = [2, 3, 5] returns 0, because every element has an even number of divisors.

Constraints

• 1 <= nums.length <= 100000
• 1 <= nums[i] <= 1000000000