Vehicle Fleet Combinations

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an integer W representing a total number of wheels. You have an infinite supply of two-wheeled and four-wheeled vehicles.

Your task is to find the number of different ways to choose a fleet of vehicles such that the total number of wheels is exactly W. Two ways are considered different if they use a different number of two-wheeled vehicles or a different number of four-wheeled vehicles.

You will be given T independent queries, each with a different value for W.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer T, the number of test cases (queries).

The next T lines each contain a single integer W, the total number of wheels for that query.

Output Format:

For each query, print a single integer on a new line representing the number of valid vehicle combinations.

Note:

The problem can be modeled by the equation 2*x + 4*y = W, where x is the number of two-wheelers and y is the number of four-wheelers.

Since 2x and 4y are both even, their sum W must also be even. If W is an odd number or less than 2, no solution is possible (except for W=0, which has one solution: zero vehicles).

For a valid (non-negative, even) W, the equation can be simplified by dividing by 2: x + 2*y = W/2.

Rearranging gives x = W/2 - 2*y. Since x must be non-negative (x >= 0), we have W/2 - 2*y >= 0, which means y <= W/4.

Therefore, the number of possible values for y (the number of 4-wheelers) ranges from 0 to floor(W/4). The number of ways is simply floor(W/4) + 1.

Sample Input 1:

Sample Output 1:

2
0
2

Explanation for Sample 1:

Query 1 (W=4): `W` is even. The number of ways is `floor(4/4) + 1 = 1 + 1 = 2`. (Combinations: one 4-wheeler, or two 2-wheelers).
Query 2 (W=5): `W` is odd. It's impossible to form this sum. The number of ways is 0.
Query 3 (W=6): `W` is even. The number of ways is `floor(6/4) + 1 = 1 + 1 = 2`. (Combinations: one 4-wheeler & one 2-wheeler, or three 2-wheelers).

Sample Input 2:

1
10

Sample Output 2:

Explanation for Sample 2:

For W=10, the number of ways is `floor(10/4) + 1 = 2 + 1 = 3`.
The combinations are:
1.  y=0 (zero 4-wheelers) -> x=5 (five 2-wheelers)
2.  y=1 (one 4-wheeler) -> x=3 (three 2-wheelers)
3.  y=2 (two 4-wheelers) -> x=1 (one 2-wheeler)

Expected Time Complexity:

The expected time complexity is O(T), as each query is solved in O(1) time.

Constraints:

1 <= T <= 10^5
0 <= W <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Vehicle Fleet Combinations

Time Complexity

Space Complexity

(100% EXP penalty)

Vehicle Fleet Combinations

Console