1.
Introduction
2.
Problem Statement
3.
Approach
4.
Pseudocode for the problem
5.
Code in Python
5.1.
Time Complexity
5.2.
Space Complexity
6.
7.
Key Takeaways
Last Updated: Mar 27, 2024

0 upvote

## Introduction

This article aims to familiarise you with the use of the basic math behind the combinations and permutations.

To brush up on your knowledge of combinations and permutations, you can read the article Permutations and Combinations on Coding Ninjas Studio.

Let’s see the problem statement in the next section.

## Problem Statement

A thief has to crack the password of the safe to open it. To open the safe, the thief has to enter the password in a different language. The language consists of K alphabets. The password is of length N, and each character of the password is present in the K alphabets of that language. Each alphabet of that language occurs at max once in the password, i.e. there is no alphabet of that language is repeated in the password.

Here the length of the password is less than K, i.e. N<=K, and the password is of at least length 1, i.e. 1<=N.

Constraints: 1<= N <=K <=105

We want to find out how many distinct passwords are possible.

Since the answer can be huge, we must find the distinct passwords modulo 109 + 7.

Let us look at some examples.

Input

``2 2``

Output

``2``

Explanation:

Here N=2 and K=2. Let the 2 characters be “a” and “b”. Since the length of the password is two and the characters in the password are unique, the distinct passwords possible are only “ab” and “ba”.

Thus output=2

Input

``2 3``

Output

``6``

Explanation:

Here N=2 and K=3. Let the K=3 characters be “a”, “b”, and “c”.

Thus the possible distinct passwords are:

ab

ac

ba

bc

ca

cb

Thus the total count of distinct passwords is 6.

Input

``3 5``

Output

``60``

Note: We will use nPr to denote permutations and nCr to denote combinations. nPrepresents the permutations of r objects selected from n objects, and nC represents the combination of r objects selected from n objects.

Also see, Euclid GCD Algorithm

## Approach

The approach is simple. As the password is of length N, we start filling each character of the password with one of the characters of that language.

The first character of the password, i.e. password[0] can be any character of the language. Thus the number of possibilities for the first character of the password is K.

For password[1], the number of possibilities is K-1 because repetition is not allowed i.e. password[1] can’t be the same as password[0].

Similarly, for password[2], the number of possibilities is K-2 because it can’t be the same as any of the first two characters of the password.

Thus for password[i], the total number of possible characters are K-i.

Thus the total number of characters = K x (K-1) x (K-2) x … x (K-(N-1)).

Thus we output (K x (K-1) x (K-2) x … x (K-(N-1))) modulo 109 + 7.

The above expression can also be written as (factorial(K)/factorial(N)) or KPN where P denotes the number of permutations. Thus the output is also KPmodulo 109 + 7.

We run a for loop to calculate this, which runs for N iterations. We multiply the distinct_passwords variable by (K-i) in the i’th iteration. Since the count of distinct_password can be huge, we calculate it modulo 109 + 7.

## Pseudocode for the problem

``````mod=10**9+7
n,k=map(int,INPUT().split())
Run i from 1 to N-1

## Code in Python

``````mod=10**9+7
n = 2
k=3
# initialized to 1
for i in range(n):
# multiplying with (k-i) possibilities at ith iteration
# taking it modulo mod as it can grow very large

Input

``2 3``

Output

``6``

### Time Complexity

The time complexity of the program is O(N).

This is because our loop runs for N iterations. For the ith iteration, we are multiplying distinct_passwords by (K-i). Also, we are taking its modulo with 109 + 7. Since the multiplication and modulo take O(1) time, the ith iteration takes O(1) time. Thus the time complexity = O(N) * O(1) = O(N).

### Space Complexity

The space complexity of the program is O(1).

This is because we are not using any extra space to store the information. Three to four variables in the code take constant space, i.e. O(1) space.

1. How is the output equal to kPmodulo 109 + 7?

As the password contains unique characters, let us choose N distinct characters from K characters. Since this can be done in KCN and the N selected characters can be arranged in N factorial ways, the answer will be KCx factorial(N) = KPN ways. Thus we output KPmodulo 109 + 7.

2. Why are we calculating the result with modulo 109 + 7?

Let us not calculate the result with modulo 109 + 7, then the output for  KPN will be very, very large as it is factorial(K)/factorial(N) since we know that the factorial grows very fast, which might lead to integer overflow. You can also verify the outputs for the program by commenting on the line distinct_passwords%mod line.

3. How is the time complexity for each iteration O(1)?

Each iteration involves multiplication and modulo operations. Since the multiplication is carried out internally by the hardware it is highly optimized. The reason is it is used almost everywhere. So each iteration takes constant time or O(1) time.

4. What is the relationship between kPn and kCn?

The kPn = factorial(k)/factorial(k-n) while kCn = factorial(k)/(factorial(k-n)*factorial(n))  Thus kPkCn x (n)!

The reason is that during permutation we select and permute them too. So arranging the n elements can be done in factorial(n).

5. What is 10**9+7 in the code?

In some languages like python double star represents power. So 10**9+7 represents 10 raised to 9 plus 7

## Key Takeaways

The blog aims to teach to calculate the total number of distinct passwords. Comments have been added to the code for better understanding. You can also copy the code and run it on your system on multiple inputs to understand the approach better.

Check out Coding Ninjas Studio to learn more about competitive programming, DSA, attempt mock tests, interview preparation and much more.

Happy Learning!!!

Live masterclass