Quick Overview

Count contiguous subarrays whose product has an odd number of positive divisors without constructing enormous products. Use prime-exponent parity and repeated prefix states to derive an efficient count that handles duplicate ranges and 64-bit answers.

Count Subarrays Whose Product Has an Odd Divisor Count

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Given an integer array `arr`, call a nonempty contiguous subarray special when the product of its elements has an odd number of positive divisors. Implement `countSpecialSubarrays(arr)` and return the total number of special subarrays. Subarrays with different starting or ending indices count separately, even when they contain identical values. ### Input and Output - Input: an integer array `arr` of length `n`. - Output: the count of special nonempty contiguous subarrays, using a 64-bit integer type where required. - A positive divisor is a positive integer that divides the product without a remainder. ### Constraints & Assumptions - `1 <= n <= 2 * 10^5` - `1 <= arr[i] <= 200` - All elements are positive; there are no zeros or negative numbers. - The array elements are small, but a subarray's product may be much larger than a machine integer. ### Examples **Example 1** ```text arr = [4, 3, 12] Output: 3 ``` The special subarrays are: - `[4]`: product `4`, with `3` positive divisors. - `[3, 12]`: product `36`, with `9` positive divisors. - `[4, 3, 12]`: product `144`, with `15` positive divisors. The other three subarrays, `[3]`, `[12]`, and `[4, 3]`, are not special. **Example 2** ```text arr = [9, 9, 9] Output: 6 ``` All six nonempty contiguous subarrays are special. Subarrays at different positions count separately. ### Clarifying Questions to Ask - Are identical sequences at different indices counted separately? Yes. - Can elements be zero or negative? No; each is between `1` and `200`. - Can the answer exceed a 32-bit signed integer? Yes, the number of subarrays can be `n * (n + 1) / 2`. ```hint First characterize positive integers with an odd number of divisors. Then consider what information about each prime exponent matters when multiplying array elements. ``` ### What a Strong Answer Covers The answer should justify the number-theoretic characterization, represent products without multiplying them directly, and count qualifying contiguous ranges without enumerating all O(n squared) candidates. It should explain the prefix-state invariant, the empty-prefix initialization, the handling of `1`, and integer-width requirements. ### Follow-up Questions - How would the state representation change if array values could contain more distinct prime factors than fit in one machine word? - Why must the empty prefix be counted before processing the first element? - How could you count qualifying subarrays offline after computing all prefix states?

Overview: Count contiguous subarrays whose product has an odd number of positive divisors without constructing enormous products. Use prime-exponent parity and repeated prefix states to derive an efficient count that handles duplicate ranges and 64-bit answers.

Given an integer array arr, call a nonempty contiguous subarray special when the product of its elements has an odd number of positive divisors. A positive divisor is a positive integer that divides the product without remainder. Implement countSpecialSubarrays(arr) and return the number of special subarrays. Subarrays with different starting or ending indices count separately even when their values are identical. The result can exceed a 32-bit signed integer. Example 1: arr = [4, 3, 12], output 3. The special ranges are [4], [3, 12], and [4, 3, 12]. Example 2: arr = [9, 9, 9], output 6. Every nonempty range is special.

Constraints

  • 1 <= len(arr) <= 200000.
  • 1 <= arr[i] <= 200; all elements are positive integers.
  • The product may be far larger than a machine integer.
  • Count nonempty ranges by index, and return a 64-bit integer where required.

Examples

Input: ([1],)

Expected Output: 1

Explanation: One is a square, so the only range is special.

Input: ([2],)

Expected Output: 0

Explanation: Two has an even number of positive divisors.

Hints

  1. A product may have many digits even though every array value is small.
  2. The empty range is excluded from the answer.

Loading coding console...

Show the approach

Approach

A positive integer has an odd number of positive divisors exactly when it is a perfect square: divisors pair as d and product/d, with one unpaired square root. A product is square exactly when every prime exponent is even. There are fewer than 64 primes not exceeding 200, so assign one bit to each prime and represent each value by its exponent parities. A smallest-prime-factor table builds each value mask by toggling one bit from a smaller value. XOR the masks into a prefix state. A subarray product is square precisely when the states before and after it agree. Start the frequency map with state zero once for the empty prefix, add the number of prior identical states to the 64-bit answer, then record the new state. This counts each valid pair of endpoints exactly once. One has mask zero, so runs of ones and repeated square values are handled naturally. No product is multiplied.

Time complexity:
O(n + 200 log log 200)
Space complexity:
O(n + 200)