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 )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.

The first line of each test case contains three space-separated integers, ‘N’, ‘M’ and ‘K’, denoting the number of downloads and games and the total memory available, respectively.

The second line of each test case contains  ‘N’ space-separated integers denoting the memory usages of downloads in the array ‘download’.

The third line of each test case contains  ‘M’ space-separated integers denoting the memory usages of games in the array ‘game’.
Output Format: 
For each test case, print an array ‘result’, denoting the pairs of downloads and games for maximum memory usage in the following format.
result[i] = [ind1, ind2], where ind1 is the index of the download chosen and ind2 is the index of the game selected. If only one game or one download is chosen, put the other index as ‘-1’. In case no options are available, print ‘-1 -1’.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
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
Hint

Can you check all possible pairs to come up with the optimal pairs?

Approaches (2)
Brute Force

Firstly, we will check all the possible pairs exhaustively to find out the maximum permitted memory usage. Then, we will insert all optimal pairs into an array and return it.


 

The steps are as follows:

  • Initialize max_usage as the largest number less than or equal to ‘K’ from either ‘game’ or ‘ download’ array. This is to check the corner case where only a game or download is chosen.
  • Then we run a loop ‘i’ for all memory usages of downloads.
    • We run a loop ‘j’ for all memory usages of games.
      • If download[i] + game[j] is less than ‘K’ and greater than max_usages, we update max_usage to download[i] + game[j] .
  • Now, we have the max_usage. We will run two loops to find all the pairs with the sum of memory usages equal to max_usage and insert it into the ‘result’ array.
  • Make sure to check the corner case of only one game or download.
  • Return the ‘result’ array.
Time Complexity

O(N*M), where N is the length of the array ‘download’ and M is the length of the array ‘game’.


 

We are checking all downloads. And for each download; we are checking each game. Thus, the overall time complexity is O(N*M).

Space Complexity

O(N), where ‘N’ is the length of the array ‘download’.


 

As we are using an array to store results. There can be a maximum of ‘N’ pairs (we have assumed N < M). Hence, the total space complexity is O(N).

Code Solution
(100% EXP penalty)
Optimize Memory Usage
Full screen
Console