Beautiful Number Orderings
Updated
Problem statement
You have the numbers 1, 2, ..., n. Put all of them in a row, using each number exactly once. Positions are counted from 1, so the first number sits at position 1.
An ordering is beautiful when every position i and the number v placed there pass this test:
vis a multiple ofi, oriis a multiple ofv.
Return how many different beautiful orderings there are.
Function
countBeautifulPermutations(n: int) → intExamples
Example 1
n = 3return = 3Check all six orderings of 1, 2, 3 (position 1 is the first number):
[1, 2, 3]: each number equals its position, so every pair divides. Beautiful.[2, 1, 3]: position 1 holds 2 (1divides2), position 2 holds 1 (1divides2), position 3 holds 3. Beautiful.[3, 2, 1]: position 1 holds 3 (1divides3), position 2 holds 2, position 3 holds 1 (1divides3). Beautiful.[1, 3, 2],[2, 3, 1]and[3, 1, 2]each put3at position2or2at position3. Neither of 2 and 3 divides the other, so they fail.
The answer is 3.
Example 2
n = 1return = 1The only ordering is [1], and 1 divides 1.
Example 3
n = 5return = 10Position 5 can only hold 1 or 5, because 5 shares no divisor pair with 2, 3 or 4. Counting every ordering that passes the rule at all five positions gives 10.
Constraints
1 <= n <= 16
More DocuSign Online Assessment questions
- Max Sum With No Two Adjacent PicksOA · Seen Apr 2026
- Max Sum With No Two Adjacent Picks on a CircleOA · Seen Apr 2026
- Grid Path With the Most ClearanceOA · Seen May 2025
- Vehicle Mixes for a Wheel TotalOA · Seen May 2025
- Count Sales Rung Up at the Wrong PriceOA · Seen Feb 2021
- Most Disjoint Intervals From Starts and DurationsOA · Seen Feb 2021
- Fewest Fountains to Water the GardenOA · Seen Feb 2021
- Lowest Start That Keeps Running Totals PositiveOA · Seen Feb 2021
- Fewest Student Groups Within a Level GapOA · Seen Nov 2020
- Alphabetize a Word ListOA · Seen May 2020
Similar questions at other companies
- Longest Anchored Song ChainIntuit · OAIntuit interview questions
- Beautiful ArrangementMathWorks · ONSITE INTERVIEWMathWorks interview questions
- Count and Score Distinct Hat AssignmentsRoblox · ONSITE INTERVIEWRoblox interview questions
- Maximum Currency Conversion Along a Simple PathRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Maximize Valid TrainsBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Count Eight-Neighbor Unlock PatternsGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Words in Disjoint Grid PathsIndeed · PHONE SCREENIndeed interview questions
- Knights, Knaves and Their StatementsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Count Routes Through Four Shop TypesOpenAI · OAOpenAI interview questions
- Minimum Moves to Spread Stones Across a GridAmerican Express · OAAmerican Express interview questions