Last Updated: 11 May, 2021

Shopping Options

Easy

Asked in companies

Solve now

Problem statement

You are given the list of costs of pants in an array “pants”, shirts in an array “shirts”, shoes in an array “shoes”, and skirts in an array “skirts”. You are also given a budget amount ‘X’ to spend. You want to buy exactly 1 item from each list. Your task is to determine the total number of possible combinations that you can buy, given that the total amount of your purchase does not exceed your budget amount.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains five integers ‘P’, ‘Q’, ‘R’, ‘S’ and, ‘X’. Denotes the number of pants, shirts, shoes, skirts, and budget amount respectively.

The second line of each test case contains exactly ‘P’ integers. Denotes the cost of each pant.

The third line of each test case contains exactly ‘Q’ integers. Denotes the cost of each shirt.

The fourth line of each test case contains exactly ‘R’ integers. Denotes the cost of each shoe.

The fifth line of each test case contains exactly ‘S’ integers. Denotes the cost of each skirt.

Output Format :

For each test case, return an integer that represents the total number of combinations to buy that are valid according to the above conditions.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

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

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We can check all possible combinations to buy items. That can be done by maintaining a variable “answer” and iterating over all four lists in a nested way such that each pant, shirt, shoe, and skirt pair can get selected and find the sum of that pair. If sum is less than or equal to budget then increment “answer” by one. Return the “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”.

Solve now

02 Approach

We can solve this problem by generating all the combinations of pants and shirts separately and all the combinations of shoes and skirts separately. Then we can find a number of valid combinations using binary search.

First, initialize an empty array “sumOfPantsAndShirts” and then let’s find every possible combination of pants and shirts by iterating over the lists in a nested way and store the sum of every combinations in an array “sumOfPantsAndShirts”. Now, sort the array “sumOfPantsAndShirts”.

Now, let’s find every possible combination of shoes and skirts by iterating over the lists in a nested way. Now, we have to find how many pant and shirt combinations are there which gives a sum less than or equal to the budget amount with the sum of that combination of shoes and skirts. This can be done by performing the binary search over the sorted array “sumOfPantsAndShirts”.

First, find the remaining amount by subtracting the cost of the shoe and skirt of that combination from the budget amount. Then find the number of shirt and pant combinations that are less than or equal to the remaining amount using binary search. In binary search, if the value of that index is less than or equal to the remaining amount then move the index to right else move the index to left.

Algorithm:

Create an integer “answer” equal to 0.
Create an empty array “sumOfPantsAndShirts”.
First iterate over the list of pants, for each pant:
- Then, iterate over the list of shirts, for each shirt:
  - Store the sum in the array “sumOfPantsAndShirts”.
Then, iterate over the list of shoes, for each shoe:
- Then, iterate over the list of skirts, for each skirt:
  - Remaining sum = budget - the cost of the shoe - the cost of the skirt
  - Find the number of combinations less than or equal to the remaining sum in the array “sumOfPantsAndShirts” using binary search.
  - In the binary search, maintain two variables “left” = 0 and “right” = size of “sumOfPantsAndShirts”.
  - While left is less than right do:
    - mid = (left + right) / 2;
    - If the value at index mid is less than or equal to the remaining sum, do left = mid + 1;
    - Else do right = mid;
  - Number combinations less than or equal to the remaining sum will be stored in the variable “left”.
  - Add the value of left in the answer.
Return “answer”.

Solve now