Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Optimize Memory Usage

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in companies
ArcesiumAmazonSamsung

Problem statement

Alex has a computer with ‘K’ memory spaces. He has a list of ‘N’ different document downloads that he would like to do, each of which consumes some unique memory usage. He also has ‘M’ computer games, each of which consumes some unique memory usage. His computer can allow at most one download and at most one game to run simultaneously, provided that the sum of memory usages doesn’t exceed ‘K’. Alex wants to play at most one game and complete at most one download so that the total memory usage is maximum.

Given a list ‘download’ and a list ‘game’, help Alex find out the number of pairs of downloads and games such that the sum of memory usages is maximum. It can also be possible that Alex only plays a game or performs a download at a time.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N, M <= 10^5
1 <= K <= 10^9
1 <= game[i], download[i] <= 10^6

Time Limit: 1 sec
Sample Input 1:
2
6 7 6
1 7 2 4 5 6
2 3 4 1 5 8 10
4 3 8
2 1 5 9
9 2 4
Sample Output 1:
0 4
2 2
3 0
4 3
5 -1
2 1
Explanation for Sample Input 1:
In test case one, if we check the pairs, we can see that the maximum permitted memory that we can use is 6. The pairs (0, 4), (2, 2), (3, 0), and (4, 3) sum up to 6 memory usages. Also, download number 5 will alone consume 6 memory. So, pair (6, -1) is also valid.
In test case two, the maximum permitted memory usage is 7. Only pair (2, 1) sum up to 7 memory usages.
Sample Input 2:
3
2 3 4
1 3
3 1 10
5 6 2
1 3 5 7 9
1 3 5 7 9 11
1 3 5
3
1 2 3
Sample Output 2:
0 0
1 1
0 0
0 1
Full screen
Console