Distinct Passwords

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.

The total number of distinct passwords= (possible characters at password[0]) x (possible characters at password[1]) x … x (possible characters at password[N-1]).

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 10⁹ + 7.

The above expression can also be written as (factorial(K)/factorial(N)) or ^KP_N where P denotes the number of permutations. Thus the output is also ^KP_N modulo 10⁹ + 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 10⁹ + 7.

Pseudocode for the problem

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

Code in Python

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

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 10⁹ + 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.

Frequently Asked Questions

1. How is the output equal to ^kP_n modulo 10⁹ + 7?

As the password contains unique characters, let us choose N distinct characters from K characters. Since this can be done in ^KC_N and the N selected characters can be arranged in N factorial ways, the answer will be ^KC_N x factorial(N) = ^KP_N ways. Thus we output ^KP_N modulo 10⁹ + 7.

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

Let us not calculate the result with modulo 10⁹ + 7, then the output for  ^KP_N 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 ^kP_{n and} ^kC_n?

The ^kP_{n = factorial(k)/factorial(k-n) while} ^kC_{n = factorial(k)/(factorial(k-n)*factorial(n))}  Thus ^kP_n = ^kC_{n 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!!!