Permutation Coefficient Problem

Problem Statement

Given two integers n and k, compute the Permutation Coefficient P(n, k), which is the number of ways to arrange k items chosen from n items where order matters. P(n, k) = n! / (n - k)!

Example:

• Input: n = 10, k = 2
• Output: 90 (10 × 9 = 90)

Noob-Friendly Explanation

Imagine you have 10 runners in a race and you want to know how many ways the top 2 positions (gold and silver) can be filled. The gold medal can go to any of 10 runners, and then silver can go to any of the remaining 9 — so 10 × 9 = 90 ways. Unlike combinations, order matters here (Runner A getting gold and B silver is different from B getting gold and A silver).

Approach 1: Brute Force (Using Factorials)

Intuition

Directly compute P(n, k) = n! / (n - k)! by calculating both factorials and dividing. This is straightforward but can overflow for large numbers.

Algorithm

1. Calculate n! (factorial of n)
2. Calculate (n - k)! (factorial of n - k)
3. Return n! / (n - k)!

public class Solution {
    public long permutationCoeff(int n, int k) {
        long numerator = factorial(n);
        long denominator = factorial(n - k);
        return numerator / denominator;
    }

    private long factorial(int num) {
        long result = 1;
        for (int i = 2; i <= num; i++) {
            result *= i;
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n) - We compute factorial up to n
• Space Complexity: O(1) - Only a few variables used

Approach 2: Optimal (Direct Multiplication)

Intuition

We don't need full factorials. P(n, k) is simply the product of k consecutive numbers starting from n going down: n × (n-1) × (n-2) × ... × (n-k+1). This avoids computing large factorials and the division entirely.

Algorithm

1. Start with result = 1
2. Multiply result by n, then n-1, then n-2, ..., do this k times
3. Return result

public class Solution {
    public long permutationCoeff(int n, int k) {
        long result = 1;

        // P(n, k) = n * (n-1) * (n-2) * ... * (n-k+1)
        for (int i = 0; i < k; i++) {
            result *= (n - i);
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: O(k) - Single loop running k times (and k ≤ n, so O(n) in worst case)
• Space Complexity: O(1) - Only one variable used