Kevin and the tower of coins

Moderate
0/80
Average time to solve is 25m
3 upvotes
Asked in companies
UberAmazonExpedia Group

Problem statement

Kevin has ‘N’ coins. Each coin has a specific width and diameter. Kevin wants to build a tower using these coins such that each coin in the tower has strictly less width and diameter as compared to all coins placed below this coin.

You have to find the maximum height of the tower that Kevin can build by using these coins.

Note:

The height of the tower is calculated by adding the width of all the coins used in the formation of this tower.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the number of coins available.

The next ‘N’ lines contain the two space-separated integers “ARR[i][0]” and “ARR[i][1]”, where “ARR[i][0]” is the width of the ‘i-th’ coin and “ARR[i][1]” is the diameter of the ‘i-th’ coin.
Output Format: 
For each test case, return the maximum possible height of the tower.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4
1 <= ARR[i][0] and ARR[i][1] <= 10^5

Time limit: 1 sec
Sample Input 1:
2
2
4 5
2 4
4
1 1
2 2
3 3
4 4
Sample Output 1:
2
4
Explanation of sample input 1:
In the first test case, the tower formed will have the 2nd coin at the lowest level and the 1st coin on top of it.

In the second test case, the 4th coin will be placed at the bottom of the tower, on top of that is 3rd and on whose top is 2nd and at the topmost level is 1st coin.
Sample Input 2:
2
1
5 4
3
4 2
6 1
1 10
Sample Output 2:
1
1
Explanation for sample input 2:
In the first test case, the tower will only be formed by a single given coin.

In the second test case, the tower will only be formed by using a single coin.
Hint

As each coin in the tower has strictly less width and diameter as compared to all coins placed below this coin, the problem boils down to finding an increasing subsequence satisfying the given constraints. Think of a recursive solution.

Approaches (3)
Recursion

The basic idea is to first sort the given array/list of integers in the increasing order of width and then just find the longest increasing subsequence of coins on the basis of their diameter. 

 

We are here using a helper function that is recursive in nature and it is used to find the LIS (Longest Increasing Subsequence) of coins on the basis of diameter.

int helper(vector<vector<int>> &arr, int previous, int current)

Where ‘ARR’ is the vector/list of pairs of integers that contain all the given coins (width of the coins of first and diameter on second), ‘PREVIOUS’ is the maximum diameter of the previous coins, and ‘CURRENT’ is the index of the current coin.

 

There will be two types of recursive calls: first, in which we will consider picking the current coin and second, in which we drop the current coin.

 

The steps are as follows:

 

  1. In the 'HELPER' function
    • If ‘CURRENT’ becomes equal to the length of 'ARR' return 0;
    • Create two variables ‘PICK’ and ‘DROP’ to store the result of two recursive calls. Initialise both of them by 0.
    • If the current coin has a diameter greater than 'PREVIOUS' then store the result of HELPER(ARR, ARR[CURRENT][1], CURRENT + 1) in ‘PICK’ and increment it by 1.
    • Store the result of HELPER(ARR, PREVIOUS, CURRENT + 1) in ‘DROP’.
    • Return the maximum between ‘PICK’ and 'DROP'.
  2. In the given function
    • Sort the vector so that all the coins become arranged in the increasing order of their width.
    • Return the result of HELPER(ARR, INT_MIN, 0).
Time Complexity

O(2^N), where ‘N’ is the total number of coins.

 

The height of the recursion tree goes up to ‘N’ and at each step, there are two recursive calls so the overall time complexity will be O(2^N).

Space Complexity

O(N), where ‘N’ is the total number of coins.

 

Since the height of the recursion tree goes up to ‘N’ and so, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Kevin and the tower of coins
Full screen
Console