FastPrepCount Subarrays with a Perfect-Square Product
Problems/Count Subarrays with a Perfect-Square Product

Count Subarrays with a Perfect-Square Product

Microsoft logoMicrosoft● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This is the first coding question of a Microsoft new-grad online assessment. The report gives the complete task. It is to count the contiguous subarrays whose product has an odd number of positive divisors. It also gives the function name, the array length limit, the value limit, a worked example, and one sample input.

Both of the report's examples appear here. The third example is ours. The answer is returned as a 64-bit integer, as the report's return type says.

Our version is about 98% the same as the reported question.

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[]) → long

Examples

Example 1

arr = [4,3,12]return = 3

Of 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 = 6

Every 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 = 1

Only [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^5
  • 1 <= 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)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public long countSpecialSubarrays(int[] arr) {
        // Write your code here.
    }
}
Checking account…