How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Turing.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Turing during technical interviews.

Count permutations with exactly n inversions

Q: Count permutations with exactly n inversions

This Coding & Algorithms question evaluates combinatorial counting and algorithmic skills related to permutations and inversion counts, emphasizing dynamic programming and modular arithmetic for large-result handling.

Company: Turing

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two integers **m** and **n**. Consider all permutations of the array `[1, 2, ..., m]` (each number from 1 to m appears exactly once). A permutation `perm` (0-indexed) has an **inversion** pair `(x, y)` if: - `0 <= x < y < m`, and - `perm[x] > perm[y]` A permutation is called **special** if it contains **exactly `n` inversions**. Return the **number of special permutations** modulo **10^9 + 7**. #### Examples 1) **Input:** `m = 3, n = 0` **Output:** `1` **Explanation:** Only `[1, 2, 3]` has 0 inversions. 2) **Input:** `m = 3, n = 1` **Output:** `2` **Explanation:** `[1, 3, 2]` and `[2, 1, 3]` each have exactly 1 inversion. #### Constraints - `1 <= m <= 1000` - `0 <= n <= 1000`

Quick Answer: This Coding & Algorithms question evaluates combinatorial counting and algorithmic skills related to permutations and inversion counts, emphasizing dynamic programming and modular arithmetic for large-result handling.

You are given two integers `m` and `n`. Consider all permutations of the array `[1, 2, ..., m]` (each number from 1 to m appears exactly once). A permutation `perm` (0-indexed) has an **inversion** pair `(x, y)` if: - `0 <= x < y < m`, and - `perm[x] > perm[y]` A permutation is called **special** if it contains **exactly `n` inversions**. Return the **number of special permutations** modulo **10^9 + 7**. #### Examples 1) **Input:** `m = 3, n = 0` -> **Output:** `1` (only `[1, 2, 3]` has 0 inversions). 2) **Input:** `m = 3, n = 1` -> **Output:** `2` (`[1, 3, 2]` and `[2, 1, 3]`). #### Constraints - `1 <= m <= 1000` - `0 <= n <= 1000` #### Approach Let `dp[i][j]` be the number of permutations of `i` elements with exactly `j` inversions. Inserting the `i`-th element into a permutation of `i-1` elements can create between `0` and `i-1` new inversions, so `dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k]`. The inner sum is a sliding window, so maintain a prefix-sum array to evaluate each state in O(1), giving an overall O(m*n) time / O(n) space algorithm.

Constraints

1 <= m <= 1000
0 <= n <= 1000
Answer is returned modulo 10^9 + 7

Examples

Input: (3, 0)

Expected Output: 1

Explanation: Only [1, 2, 3] has 0 inversions.

Input: (3, 1)

Expected Output: 2

Explanation: [1, 3, 2] and [2, 1, 3] each have exactly 1 inversion.

Input: (3, 2)

Expected Output: 2

Explanation: [2, 3, 1] and [3, 1, 2] each have exactly 2 inversions.

Input: (3, 3)

Expected Output: 1

Explanation: Only [3, 2, 1] (fully reversed) has the maximum 3 inversions for m=3.

Input: (1, 0)

Expected Output: 1

Explanation: The single permutation [1] has 0 inversions.

Input: (1, 1)

Expected Output: 0

Explanation: A single-element permutation can never have an inversion, so no permutation has exactly 1.

Input: (4, 3)

Expected Output: 6

Explanation: Six of the 24 permutations of [1,2,3,4] have exactly 3 inversions.

Input: (5, 5)

Expected Output: 22

Explanation: 22 permutations of [1..5] have exactly 5 inversions.

Input: (10, 10)

Expected Output: 21670

Explanation: Larger case validating the O(m*n) DP and prefix-sum window.

Input: (1000, 0)

Expected Output: 1

Explanation: For any m, exactly one (the sorted) permutation has 0 inversions; confirms the m boundary.

Hints

Define dp[i][j] = number of permutations of i elements with exactly j inversions. The answer is dp[m][n].
Inserting the largest element into a permutation of i-1 elements at the position that leaves k elements to its right adds exactly k new inversions, with 0 <= k <= i-1. So dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k].
The inner summation is a sliding window of width i over the previous row. Use a prefix-sum array to compute each new[j] in O(1), reducing the total work to O(m*n). Take care with the modulo on subtraction (add MOD or rely on Python's non-negative modulo).

Quick Overview

This Coding & Algorithms question evaluates combinatorial counting and algorithmic skills related to permutations and inversion counts, emphasizing dynamic programming and modular arithmetic for large-result handling.