Count Divisible Permutations
Updated
Problem statement
SDE-1
Suppose you have n integers from 1 through n. A permutation of those n integers is considered a Divisible Permutation if for every i, where 1 <= i <= n, either of the following is true:
perm[i]is divisible byi.iis divisible byperm[i].
Given an integer n, find the total number of the valid Divisible Permutations.
Note - you may want to refer to LC 810
Function
countDivisiblePermutations(n: int) → intExamples
Example 1
n = 2return = 2The first Divisible Permutation is [1,2]: permutation[1] = 1 is divisible by i = 1 permutation[2] = 2 is divisible by i = 2 The second Divisible Permutation is [2,1]: permutation[1] = 2 is divisible by i = 1 i = 2 is divisible by permutation[2] = 1
Constraints
- 1 <= n <= 15
More Deloitte interview questions
- Second-Highest Distinct SalaryPHONE SCREEN · Seen Jul 2026
- Check AnagramsONSITE INTERVIEW · Seen Jun 2026
- Seventh Nearest PalindromeOA · Seen May 2026
- Minimum Deletions for a Non-PalindromeOA · Seen Jul 2025
- Minimum-Cost Solar Rooftop AllocationOA · Seen Jul 2025
- Pair Elements with Even SumsOA · Seen Jul 2025
- Largest Element in an ArrayOA · Seen Nov 2024
- Install Carbon FiltersOA · Seen Oct 2023
- Longest Substring with Even OccurrencesOA · Seen Oct 2023
- Maximum Sum RectangleOA · Seen Apr 2022
Similar questions at other companies
- Optimize Discount Selection Under a Point BudgetPalantir · OA
- Count Routes Through Four Shop TypesOpenAI · OA
- Minimum Stores for a Shopping ListWhatNot · PHONE SCREEN
- Delete K Subsets for Maximum ScoreRubrik · OA
- Count Prefix Subsets with a Given XORGoDaddy · OA
- Maximum Index-Weighted Sum with Disjoint SwapsVisa · OA
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OA
- Pressure-Isolation Shutdown OrderIntuit · OA
- Distinct Bitwise-OR Scores of Increasing SubsequencesWalmart · OA
- Stable Workload Redistribution TreesTower Research Capital · OA