Shopping Options Problem Statement

Given arrays representing the costs of pants, shirts, shoes, and skirts, and a budget amount 'X', determine the total number of valid combinations that can be purchased such that the total cost does not exceed 'X'. Each purchase must include exactly 1 item from each list.

Input:

The first line contains an integer ‘T’ denoting the number of test cases. Each test case consists of: - Five integers ‘P’, ‘Q’, ‘R’, ‘S’, and ‘X’, representing the number of pants, shirts, shoes, skirts, and the budget amount, respectively. - The second line contains ‘P’ integers, denoting the cost of each pant. - The third line contains ‘Q’ integers, denoting the cost of each shirt. - The fourth line contains ‘R’ integers, denoting the cost of each shoe. - The fifth line contains ‘S’ integers, denoting the cost of each skirt.

Output:

For each test case, return an integer that represents the total number of valid combinations. Each result should be output on a new line.

Example:

Example input not provided in the original prompt.

Constraints:

1

Question

Shopping Options Problem Statement

Given arrays representing the costs of pants, shirts, shoes, and skirts, and a budget amount 'X', determine the total number of valid combinations that can be purchased such that the total cost does not exceed 'X'. Each purchase must include exactly 1 item from each list.

Input:

The first line contains an integer ‘T’ denoting the number of test cases. Each test case consists of:
 - Five integers ‘P’, ‘Q’, ‘R’, ‘S’, and ‘X’, representing the number of pants, shirts, shoes, skirts, and the budget amount, respectively.
 - The second line contains ‘P’ integers, denoting the cost of each pant.
 - The third line contains ‘Q’ integers, denoting the cost of each shirt.
 - The fourth line contains ‘R’ integers, denoting the cost of each shoe.
 - The fifth line contains ‘S’ integers, denoting the cost of each skirt.

Output:

For each test case, return an integer that represents the total number of valid combinations. Each result should be output on a new line.

Example:

Example input not provided in the original prompt.

Constraints:

1 <= T <= 100
1 <= P, Q, R, S <= 10
1 <= X <= 10^9
1 <= pants[i], shirts[i], shoes[i], skirts[i] <= 10^9

Note:

You do not need to print anything. Focus on implementing the required function to return the results.

Accepted Answer

Algorithm:

Create an integer “answer” equal to 0.

First iterate over the list of pants, for each pant:

Then, iterate over the list of shirts, for each shirt:

Then, iterate over the list of shoes, for each shoe:

Then, iterate over the list of skirts, for each skirt:

If the sum of cost of pant, shirt, shoe, and skirt is less than or equal the amount of budget, then increment the answer by one.

Else do nothing.

Return “answer”.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Time Complexity: O(1)Explanation:

O(P * Q * R * S), where ‘P’, ‘Q’, ‘R’, and ‘S’ denote the number of pants, shirts, shoes, skirts respectively.

Since we are checking all possible combinations iterating over all four lists in a nested way. Therefore time complexity is O(P * Q * R * S).

Java (SE 1.8)

/*

Time Complexity: O(P * Q * R * S)

Space Complexity: O(1)

Where 'P', 'Q', 'R', and 'S' denote the number of pants, shirts, shoes, skirts respectively.

*/

public class Solution

{

public static int shoppingOptions(int[] pants, int[] shirts, int[] shoes, int[] skirts, int budget)

{

//To store number of ways to buy

int answer = 0;

// To generate every possible combinations

for (int i = 0; i < pants.length; i++)

{

for (int j = 0; j < shirts.length; j++)

{

for (int k = 0; k < shoes.length; k++)

{

for (int l = 0; l < skirts.length; l++)

{

if (pants[i] + shirts[j] + shoes[k] + skirts[l] <= budget)

{

answer = answer + 1;

}

return answer;

}