Number Of Vehicles

Easy
0/40
Average time to solve is 15m
profile
Contributed by
26 upvotes
Asked in companies
Tata Consultancy Services (TCS)AccentureMicrosoft

Problem statement

There is a person named Bob who is the mayor of a state. He wants to find the maximise number of vehicles that can be registered in his state.

A vehicle normally has a registration number like ST 01 AB 1234. Each registration number has four parts, separated by spaces. The first part has two letters common for all cars in the state. The next two-digit number is the number of the district where the car is registered within the state. It is always two digits and may have a leading zero. After that, the next part consists of two letters (AB), with each letter selected from a range, denoting the series and the last part is a 4-digit number this will always be four digits, even if it has leading zeros).

The entire registration number is unique to each vehicle. You have been given the number of districts in the state, a range of letters to be used in the series and a set of digits that can be used for forming a vehicle registration number.

Your task is to find the maximum number of vehicles that can be registered in Bob’s state.

Note :

1. No two vehicles can have the same registration number. 
2. Two registration numbers are said to be different if they have at least a different character or a digit at the same location. For eg. DL 05 AC 1234 and DL 05 AC 1235 are different, DL 05 AC 1234 and DL 05 AB 1234 are different registration numbers. 
3. All the cars will have the same first two characters as they have to be registered in the same state.
4. The numbering of the districts in the state starts from ‘1’ (which will obviously be written as 01 in registration number).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains a single integer 'districtCount', denoting the number of districts in the state.

The second line of each test case contains four space-separated characters 'ALPHA1', 'ALPHA2', 'ALPHA3' and 'ALPHA4' , denoting the range of the first alphabet and second alphabet of the series. The range for first and the second alphabet will be [ALPHA1, ALPHA2] and [ALPHA3, ALPHA4] respectively.

The third line of each test case contains four space-separated integers 'DIG1', 'DIG2', 'DIG3' and 'DIG4' denoting the range of last 4 digits in the vehicle registration number. The ranges will be [0, DIG1], [0, DIG2], [0, DIG3] and [0, DIG4] respectively.
Output Format : 
The only line of output of each test case consists of an integer, the maximum number of vehicles that can be registered in the state.
Note : 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10^4
1 <= Number of districts < 10^2
A <= Range of alphabets <= Z
0 <= Range of digits <= 9
ALPHA1 <= ALPHA2 and ALPHA3 <= ALPHA4

The width of the district column will always be equal to 2.

Time Limit: 1 sec.
Sample Input 1 :
1
4
A C B D
5 4 3 4
Sample Output 1 :
21600
Explanation For Sample Input 1 :

altImage

There are 4 possibilities for district numbers(12,13,14 and 15) and each district has 3 possibilities for first alphabet of series(A, B, and C) and 3 possibilities for second alphabet of series(B, C and D), and now each series has 6 possibilities for first digit(from left) of the registration number(0,1,2,3,4,5), 5 possibilities for second digit(0,1,2,3,4), 4 possibilities for third digit(0,1,2,3) and 5 possibilities for the last digit(0,1,2,3,4). So overall the maximum number of distinct vehicle registration number possible are: 4*3*3*6*5*4*5 = 21600.
Sample Input 2 :
1
2
A B C D
2 3 2 3
Sample Output 2 :
1152
Explanation For Sample Input 2 :

altImage

There are 2 possibilities for district numbers(10, and 11) and each district has 2 possibilities for first alphabet of series(A, and B) and 2 possibilities for second alphabet of series(C and D), and now each series has 3 possibilities for first digit(from left) of the registration number(0,1,2), 4 possibilities for second digit(0,1,2,3), 3 possibilities for third digit(0,1,2) and 4 possibilities for the last digit(0,1,2,3). So overall the maximum number of distinct vehicle registration number possible are: 2*2*2*3*4*3*4 = 1152.
Hint

Basic Mathematics

Approaches (1)
Permutation and Combinations
  1. We can make use of basic Permutation and combination, to find out how many distinct vehicle registration numbers are possible.
  2. Consider that we have 4 locations to fill with some digits and each location can acquire some digit from 0 to 9. Then the total possible ways to fill all locations in unique ways will be 10 X 10 X 10 X 10, as each location can acquire 10 different types of digits. In the same way, we will calculate the possibilities at each location of the registration number and then use the principle of counting to find the number of unique registrations.

 

Here is the algorithm :

 

  1. The first part(State) is fixed, so we need not do anything with that.
  2. Now, let us count the total possibilities for the second part(no. ff districts) (say, ‘D’).
  3. Then the possible values for the 3rd part can be calculated with the help of principle of counting since we have 2 characters and let the range of the first character be 'A'(i.e a total of ‘A’ number of characters are allowed in this place) and that of the second character be ‘B’, so the total possible values for the 3rd part are ‘S' is equal to ‘A’*'B'.
  4. Similarly, we can calculate for the 4th part, with the help of principle of counting and it comes out to be ‘R’ equal to  ‘A’*'B'*'C'*'D', where ‘A’ is the range of 1st digit, ‘B’ is the range of 2nd digit, ‘C’ is the range of 3rd digit and ‘D’ is the range of 4th digit.
  5. So the total possible number of vehicles that can be registered in the state can be calculated as ‘D’*'S'*'R'. Because we have ‘R’ registration numbers in each series so in ‘S’ series we have ‘S’*'R' possible registration numbers, then we have ‘S’ series in a district so in 'D' districts we have ‘D’*'S' series, so the total possible registration numbers are 'D'*'S'*'R'.
Time Complexity

O(1)

 

All operations are performed in constant time. Hence, the overall time complexity will be O(1).

Space Complexity

O(1)

 

We are not using any extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Number Of Vehicles
Full screen
Console