Count Subarrays with a Perfect-Square Product
Updated
Problem statement
You are given an integer array arr. A contiguous subarray is special if the product of its elements has an odd number of positive divisors.
Return the number of special subarrays. Subarrays that start or end at different indices are counted separately, even when their values are the same.
Function
countSpecialSubarrays(arr: int[]) → longExamples
Example 1
arr = [4,3,12]return = 3Of the six subarrays, three have a perfect-square product: [4] with product 4, [3, 12] with product 36, and [4, 3, 12] with product 144. These have 3, 9, and 15 divisors. The products 3, 12, and 12 of the other three subarrays are not squares.
Example 2
arr = [9,9,9]return = 6Every product is a power of 9, which is always a perfect square, so all 6 subarrays are special.
Example 3
arr = [2,3,6,5]return = 1Only [2, 3, 6] works: its product is 36 = 6^2. Every other subarray has some prime that appears an odd number of times, for example [2, 3, 6, 5] has product 180 = 2^2 * 3^2 * 5.
Constraints
1 <= arr.length <= 2 * 10^51 <= arr[i] <= 200
More Microsoft Online Assessment questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
- Count Digit Replacements with No Equal Adjacent DigitsOA · Seen Oct 2026
Similar questions at other companies
- Count Subarrays With Given XORInMobi · OAInMobi interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
- Calculate the Sum After Range TogglesBlink Health · OA
- Minimum Power-of-Two Removal OperationsIBM · OAIBM interview questions
- Count Attack Vectors by Divisor RangeVisa · OAVisa interview questions
- Maximum Equal Parts for PrefixesAmazon · OA
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Get Triplet CountPoint72 · OAPoint72 interview questions
Microsoft interview experiences
- Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
- Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)