Count Ideal Arrays
Updated
Problem statement
Count the distinct integer arrays arr of length n such that every entry is between 1 and maxValue, inclusive, and every entry after the first is divisible by the immediately preceding entry.
Equal neighboring values are allowed. Arrays are distinct when some position has a different value; repeated values within an array are allowed. Return the count modulo 1000000007. For this exercise, length 1 is permitted and the interface returns an integer residue.
Function
countIdealArrays(n: int, maxValue: int) → intExamples
Example 1
n = 2maxValue = 5return = 10For length 2, the possible second values contribute their numbers of positive divisors: values 1 through 5 contribute 1,2,2,3,2 arrays, totaling 10.
Example 2
n = 3maxValue = 4return = 13Group by the last value. Ending at 1 gives one array; ending at 2 or 3 gives three each; ending at 4 gives six. The total is 1+3+3+6=13.
Constraints
- For this exercise, assume 1 <= n <= 1000.
- For this exercise, assume 1 <= maxValue <= 2000.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
- Fibonacci with Input ValidationONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Recover Coins from Change CountsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Two-Player Gambler's Ruin Probability and SimulationMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Volunteer Awards: Totals Divisible by KNutanix · ONSITE INTERVIEWNutanix interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Count Divisible Power SumsGoodScore · ONSITE INTERVIEW
- Climbing StairsAMD · ONSITE INTERVIEWAMD interview questions
- Climb Stairs with One, Two, or Three StepsAgoda · ONSITE INTERVIEWAgoda interview questions
- Tile a Three-Row Board with DominoesJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)