Katkat
Back

Count permutations with exactly n inversions

TuringSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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