Skip to main content

Math Basics

Permutation(nPr) and Combination(nCr) Solution In C++/Java/Python/JS

Introduction

In the journey of learning Data Structures and Algorithms (DSA), we often come across problems that require counting arrangements, selections, or groupings. Whether it's calculating possibilities in recursion, brute force combinations, or logic puzzles, one concept keeps popping up — Permutation and Combination.

Understanding this topic early will give you a solid mathematical foundation and help you think more clearly when approaching complex problems later. Let’s break it down step by step.

What is a Permutation?

Permutation refers to the arrangement of items where the order matters.

permutation relates to the act of arranging all the members of a set into some sequence or order. In other words, if the set is already ordered, then the rearranging of its elements is called the process of permuting. Permutations occur, in more or less prominent ways, in almost every area of mathematics. They often arise when different orderings on certain finite sets are considered.

Let’s say you have 3 letters: A, B, and C. If you want to arrange 2 of them at a time, you can form:

  • AB
  • BA
  • AC
  • CA
  • BC
  • CB

That gives us 6 different arrangements, even though the letters are the same — because their order is different.

Real-life Examples:

  • Password combinations where order matters
  • Ranking participants in a race (1st, 2nd, 3rd)
  • Arranging books on a shelf

Formula:

nPr = n! / (n - r)!
where:

  • n = total number of items
  • r = number of items being arranged
  • ! = factorial (e.g., 5! = 5 × 4 × 3 × 2 × 1)

Example:
How many 3-digit numbers can be formed using the digits 1, 2, 3, 4 with no repetition?

Here,

  • n = 4 (digits)
  • r = 3 (you want 3-digit numbers)

4P3 = 4! / (4 - 3)! = 24/1 = 24

So, you can form 24 unique numbers.

What is a Combination?

Combination is about selecting items where the order doesn’t matter.

The combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases, it is possible to count the number of combinations. Combination refers to the combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms k-selection or k-combination with repetition are often used.

Using the same letters A, B, and C, if you want to select 2 at a time, you only get:

  • AB
  • AC
  • BC

(Note: AB and BA are considered the same in combinations.)​

Real-life Examples:

  • Selecting players for a team
  • Picking lottery numbers
  • Choosing 3 questions out of 10 for a test

Formula

nCr = n!​ / r!(n-r)!

Where:

  • n = total number of items
  • r = number of items being selected

Example:
From a group of 5 students, in how many ways can you choose 2 students to represent the class?

Here,

  • n = 5
  • r = 2

5C2 = 5!/2!(5−2)! = 120 / 2 * 6 = 10

So, there are 10 possible pairs of students.

Key Difference: Permutation vs Combination

Order Matters:

  • In Permutation, the order of items matters.
    (AB and BA are considered different)
  • In Combination, the order does not matter.
    (AB and BA are considered the same)

Use Case:

  • Use Permutation when you're dealing with arrangements, rankings, or placements.
  • Use Combination when you're simply selecting or choosing items without regard to order.

Example Situations:

  • Permutation: Forming passwords, assigning race positions, seating arrangements.
  • Combination: Selecting team members, picking lottery numbers, choosing questions for a quiz.

Formula Difference:

  • Permutation: nPr = n! / (n - r)!​
  • Combination: nCr = n! / r!(n - r)!

Permutation (nPr) – Factorial Method

Intuition

When you're arranging r items out of a total of n, the most important thing is that the order of arrangement matters. Think of it like this — you have n unique items and you want to fill r positions. For the first position, you have n choices. Once you pick one, you're left with n - 1 options for the second. For the third, you'll have n - 2, and so on. This continues until you've placed all r items.

This gives you a product of n × (n - 1) × (n - 2) × ... × (n - r + 1), which is essentially the first r terms of the factorial n!. The rest of the factorial terms — the ones you don't need — are from (n - r)!. So by dividing n! by (n - r)!, we get the exact number of ordered arrangements of r items out of n.

Hence, the formula:
nPr = n! / (n - r)!

Approach

  • Calculate n! — total arrangements of all n items.
  • Calculate (n - r)! — arrangements you're not using.
  • Divide the two to get the arrangements for r items.
  • Return the result.

Dry Run

Input:
n = 4
r = 3

We want to calculate:
nPr = 4P3 = 4! / (4 - 3)!

Step 1: Compute factorial(n)
factorial(4) = 4 × 3 × 2 × 1 = 24

Step 2: Compute factorial(n - r)
n - r = 4 - 3 = 1
factorial(1) = 1

Step 3: Compute nPr
nPr = factorial(4) // factorial(1) = 24 // 1 = 24

Final Output:
Permutation 4P3 = 24

So, there are 24 different ways to arrange 3 items out of 4.

Code Implementation

Code for All Languages
C++ 
// Function to calculate factorial
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; ++i)
        result *= i;
    return result;
}

// Function to calculate nPr = n! / (n - r)!
long long permutation(int n, int r) {
    if (n < r || n < 0 || r < 0)
        return 0;  // Invalid input case
    long long num = factorial(n);
    long long denom = factorial(n - r);
    return num / denom;  // This will return correct value
}

Java 
  public static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // Function to calculate nPr = n! / (n - r)!
    public static long permutation(int n, int r) {
        if (n < r || n < 0 || r < 0)
            return 0;  // Invalid input case
        long num = factorial(n);
        long denom = factorial(n - r);
        return num / denom;  // This will return correct value
    }

Python 
def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Function to calculate nPr = n! / (n - r)!
def permutation(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    num = factorial(n)
    denom = factorial(n - r)
    return num // denom  # Integer division

Time Complexity

The factorial method for calculating permutations involves computing two factorials: n! and (n - r)!. The calculation of n! requires a loop that runs n times, resulting in a time complexity of O(n). Similarly, (n - r)! is computed with a loop that runs n - r times, which is also linear but generally smaller than n. However, since these computations are done sequentially and not reused or shared, the overall time complexity is dominated by the larger of the two — that is, O(n). This makes the factorial approach simple to understand but less efficient for larger values of n.

Space Complexity

The space complexity of the factorial method is O(1), meaning it uses constant memory regardless of the size of the input. This is because the algorithm only uses a fixed number of variables to store the results of the factorial computations and the final output. There is no recursion, no array, and no dynamic allocation involved. Each factorial is computed iteratively, and only scalar values are stored throughout the process. Hence, the memory usage remains constant, making this approach space-efficient.

Bridging Factorial and Optimized Approach

While the factorial method calculates both n! and (n - r)! separately, it ends up doing more work than necessary. Most of the terms in the numerator and denominator cancel out during division. In the optimized approach, we skip the full factorials and directly multiply only the necessary r terms from n down to (n - r + 1). This eliminates redundant computations and improves efficiency.

Optimized Approach

Intuition

The factorial method calculates n! and (n - r)! entirely, even though most of those terms cancel out when divided. Instead of computing and dividing large numbers, we can directly multiply just the terms we need — the first r values starting from n and decreasing by 1. This way, we efficiently get the result of nPr without redundant computation. We’re essentially building the permutation product directly, which gives us both better performance and numerical stability.

Approach

  1. Initialize a variable result = 1.
  2. Loop from i = 0 to i < r (i.e., run for r steps).
  3. In each iteration, multiply result by (n - i).
  4. After the loop, result will contain n × (n-1) × (n-2) × ... × (n - r + 1).
  5. Return result as the value of nPr.

Dry Run

Input:
n = 4
r = 3

We are calculating 4P3 using the optimized approach.
Instead of calculating full factorials, we run a loop r times and multiply the result with (n - i) at each step.

Step 0: Initialization
We start with:
result = 1

Step 1: i = 0
Calculate: term = n - i = 4 - 0 = 4
Now update result: result = result × term = 1 × 4 = 4
→ After this step, result becomes 4

Step 2: i = 1
Calculate: term = n - i = 4 - 1 = 3
Now update result: result = result × term = 4 × 3 = 12
→ After this step, result becomes 12

Step 3: i = 2
Calculate: term = n - i = 4 - 2 = 2
Now update result: result = result × term = 12 × 2 = 24
→ After this step, result becomes 24

The loop runs for r = 3 iterations, and now result = 24

Final Output:
4P3 = 24

Code Implementation

Code for All Languages
C++ 
// Optimized function to calculate nPr
long long permutation(int n, int r) {
    if (n < r || n < 0 || r < 0)
        return 0;

    long long result = 1;
    for (int i = 0; i < r; ++i) {
        result *= (n - i);
    }
    return result;
}

Java 
   public static long permutation(int n, int r) {
        if (n < r || n < 0 || r < 0) return 0;

        long result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
        }
        return result;
    }

Python 
def permutation(n, r):
    if n < r or n < 0 or r < 0:
        return 0

    result = 1
    for i in range(r):
        result *= (n - i)
    return result

Javascript 
function permutation(n, r) {
    if (n < r || n < 0 || r < 0) return 0;

    let result = 1;
    for (let i = 0; i < r; i++) {
        result *= (n - i);
    }
    return result;
}

Time Complexity: O(n)

In the optimized approach, we calculate nPr by multiplying only the first r terms from n downward. This is done using a single loop that runs exactly r times if we consider r as n and each iteration performs one multiplication, which is a constant-time operation. Therefore, the total time taken is directly proportional to the value of r hence the time complexity will be O(n).

Space Complexity: O(1)

This method uses only a few scalar variables such as n, r, i, and result to perform the computation. No additional memory is used for arrays, recursion stacks, or dynamic data structures. Since the amount of memory used does not grow with input size, the space required remains constant regardless of n or r.

Combination (nCr) – Factorial Method

Intuition

Combination refers to selecting items from a group where order doesn’t matter. For example, choosing 2 players from a team of 5 is the same whether you pick Player A first or Player B — the selection is the same: A & B. This is different from permutations where order plays a role.

Mathematically, to compute how many ways we can choose r items from n, we use the formula:
nCr = n! / (r! × (n - r)!)

Here's why: n! gives all the possible arrangements of n items. But since order doesn’t matter in combinations, we must remove the overcounting caused by the arrangement of the selected r items — that’s why we divide by r!. We also need to ignore the arrangement of the unselected items, hence we divide by (n - r)! as well.

This formula gives us the number of unique groups of r elements from n, without considering their order.

Approach

  • Input: Take two integers, n and r
  • Check for Valid Input: If n < r or either is negative, return 0
  • Calculate Factorials:Compute n!Compute r!Compute (n - r)!
  • Apply Formula:
    Use the formula nCr = n! / (r! × (n - r)!)
  • Return the result.

Dry Run

Input:
n = 5, r = 2
We are computing 5C2.

Step 1:
Calculate n! = 5 × 4 × 3 × 2 × 1 = 120

Step 2:
Calculate r! = 2 × 1 = 2

Step 3:
Calculate (n - r)! = 3! = 3 × 2 × 1 = 6

Step 4:
Apply the formula:
nCr = 120 / (2 × 6) = 120 / 12 = 10

Output: 5C2 = 10

Code Implementation

Code for All Languages
C++ 
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; ++i)
        result *= i;
    return result;
}

long long combination(int n, int r) {
    if (n < r || n < 0 || r < 0) return 0;
    return factorial(n) / (factorial(r) * factorial(n - r));
}

Java 
public static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++)
            result *= i;
        return result;
    }

    public static long combination(int n, int r) {
        if (n < r || n < 0 || r < 0) return 0;
        return factorial(n) / (factorial(r) * factorial(n - r));
    }

Python 
def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    return factorial(n) // (factorial(r) * factorial(n - r))

Javascript 
function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

function combination(n, r) {
    if (n < r || n < 0 || r < 0) return 0;
    return Math.floor(factorial(n) / (factorial(r) * factorial(n - r)));
}

Time Complexity: O(n)

In the factorial method for calculating combinations, we compute three factorial values: n!, r!, and (n - r)!. Each of these calculations involves a simple loop that runs linearly up to the respective number. While r and n - r may be smaller than n, in the worst case they can still approach n. Therefore, the time taken is dominated by the largest factorial calculation, which is n!.

As a result, the overall time complexity of this approach is considered O(n), since we are performing up to n multiplications across the different factorials. This is acceptable for small to moderate values of n, but can become inefficient for very large inputs due to the rapid growth of factorial values.

Space Complexity: O(1)

The algorithm uses only a handful of basic variables to perform the computation: a few integers to store the intermediate factorial values and the final result. It does not require any additional data structures like arrays, stacks, or recursion, and the memory used does not depend on the input size.

Therefore, the space required remains constant regardless of the size of n or r, making the space complexity of this method O(1) — that is, it operates in constant space.

Bridge betweeen factorial and Optimized Approach

In the factorial method, we compute n!, r!, and (n - r)! separately and then divide them to get the final result. While this approach is simple, it involves computing large factorials, which may cause overflow or unnecessary multiplications, especially when n is large.

The optimized approach avoids calculating full factorials by simplifying the formula:

nCr = (n × (n - 1) × ... × (n - r + 1)) / (r × (r - 1) × ... × 1)

Here, we multiply only the necessary r terms in both the numerator and denominator, reducing the number of operations and making it much more efficient — especially for large values.

Intuition

Instead of calculating large factorials and then simplifying the result, we can build the numerator and denominator simultaneously — step by step — to keep the numbers small and avoid overflow. We only multiply the top r numbers from n downward and divide by the corresponding numbers in r!.

This technique lets us compute nCr without ever needing to calculate full factorials, which saves both time and computational effort. It is especially helpful when n is large and r is small.

Approach

  • Input: Take n and r
  • Check Validity: If n < r or if either is negative, return 0
  • Minimize r: Use r = min(r, n - r) to reduce operations
  • Initialize result = 1
  • Loop from i = 0 to r - 1At each step:
    result = result × (n - i) / (i + 1)
  • Return result

Dry Run

Input:
n = 5, r = 2

Step 1:
Use r = min(2, 5 - 2) = 2
Initialize result = 1

Iteration 1 (i = 0):
result = result × (5 - 0) / (0 + 1)
result = 1 × 5 / 1 = 5

Iteration 2 (i = 1):
result = result × (5 - 1) / (1 + 1)
result = 5 × 4 / 2 = 10

Final Output: 5C2 = 10

Code Implementation

Code for All Languages
C++ 
long long combination(int n, int r) {
    if (n < r || n < 0 || r < 0) return 0;
    if (r > n - r) r = n - r;

    long long result = 1;
    for (int i = 0; i < r; ++i) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

Java 
public static long combination(int n, int r) {
        if (n < r || n < 0 || r < 0) return 0;
        if (r > n - r) r = n - r;

        long result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }

Python 
def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)

    result = 1
    for i in range(r):
        result *= (n - i)
        result //= (i + 1)
    return result

Javascript 
function combination(n, r) {
    if (n < r || n < 0 || r < 0) return 0;
    r = Math.min(r, n - r);

    let result = 1;
    for (let i = 0; i < r; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return Math.floor(result);
}

Time Complexity-O(n)

In the worst case, the loop runs r times, and each step performs one multiplication and one division.
Even after optimizing r = min(r, n - r), in the worst case r can still be close to n/2.

So, the worst-case time complexity is:
O(r) → and at most O(n/2) = O(n) in the worst case.

Space Complexity-O(1)

The space complexity of this approach is extremely efficient. We do not use any arrays, recursion, or data structures that grow with input size. The only variables we use are for input values, a result accumulator, and a loop counter — all of which occupy constant memory.

There is no need to store intermediate factorials or any temporary lists. Thus, the space used by this algorithm does not depend on n or r, and remains fixed throughout the computation. As a result, the space complexity is O(1) — constant space.