15 months ago

The_Coder_Guy • 30

Question 1

Airlift

You and your family are trapped on a flood-prone island. When you called the emergency services to ask for assistance, they promised to send aircraft to airlift your family. As long as the combined weight of the two passengers is less than or equal to K, each aircraft is only permitted to carry a maximum of K and a maximum of two other passengers in addition to the pilot. You are given the following:
• The maximum capacity of he aircraft
• The total number of family members
• An array weights, where weights) represent the weight of the h family member
Task
Return the minimum number of aircraft required to airlift the family. If not possible, return -1.
Example
Assumptions
• K = 5
• N=9
• weights = [3, 3, 5, 2, 1, 4. 5, 1, 5]

Approach
• 6 aircraft are required with weights [3,2], [3,1] [4,1] [5] [5] [5]
Function description
Complete the Solve() function provided in the editor below. This function takes the
following 3 arguments and returns the maximum points you can get
•K: Represents the maximum weight capacity of the ajrcraft.
•N: Represents the total number of family members
•weights[]: Represents the weignt of family members
Input format
• The first line contains an integer K denoting the maximum weight capacity of the aircraft.
• The second line contains an integer N denoting the total number of family members.
• The third line contains N sace-separated integers representing the weight of family members.
Output Format
Return the minimum number of aircraft required to airlift the family if not possible return -1.
Constraints

1<=K<=10⁹

1<=N<=10⁵

1<=Weights[i]<=10⁹

weights contain only positive integers

Sample input:
6
4
3 5 4 3

Sample output:
3

Explanation

3 aircraft are required with weights[3,3][4][5]

Sample input 1 
5
5
2 4 2 1 4

Sample output 1
3

Sample input 2
7
7
8 5 2 1 4 8 3 

Sample output 2
-1

Sample input 3
2
1
1

Sample output 4
1

Question 2

Melting coins

Given N piles of gold coits represented by piles[i]. Bob needs to melt all the gold within a specified time frame H hours. He can control the melting rate, denoted by k
which is the number of coins he can melt from a pile per hour.
If a pile has fewer than k coins. he melts all of them and doesn't melt any more coins from that pile for the remaining time in that hour. The osjective is to find the
lowest integer value for k thatiallows Bob to melt ail the gold coins within H hours.

Function description
Complete the Solve() function. this function takes the following 3 arguments and finds the owest integer k thatwill allow Bob to melt all the gold coins in H hours
• N: Represents the number of piles of gold coins
• H: Represents the time in which meltirg should be done
• piles: Represents an array of integers where piles[i] represent the number of coins in the ith pile

Input Format

•The first line contains an integer N denoting the number of piles of gold coins.
• The second line contains an integer H denoting the time in hours in which melting
should be done.
• The second line contains an N space-separated integer piles where piles[1] represent the number of coins in the ith pile.

Output format
Return the lowest integer k that will allow Alice to melt all the gold coins in h hours.
Constraints
1 ≤ N≤10⁴
0≤H ≤10⁹
N≤H
0 ≤ piles [i] ≤ 10⁹

Sample Input
4
8
3 6 7 11

Sample Output
4

Explanation
Given
N=4
H=8
piles = [3, 6, 7, 11]
Approach
For k =4,
H=1--> First pile --> piles =[3-3, 6, 7, 11] --> [0, 6, 7, 11]
H=2--> Second pile--> piles=[0, 6-4, 7, 11] -->[0 ,2, 7, 11]
H=3--> Second pile -->piles =[0, 2-2, 7,11] --> [0,0,7,11]
H=4 -->Third pile --> piles=[0, 0, 7-4, 11] -->[0, 0, 3, 11]
H=5 --> Third pile --> piles=[0,0, 3-3, 11] --> [0, 0, 0, 11]
H=6 --> Fourth pile --> piles=[0, 0, 0, 11-4]-->[0,0,0,7]
 H=7 --> Fourth pile -> piles=[0, 0, 0, 7-4] --> [0, 0, 0, 3]
.H=8 --> Fourth pile --> piles=[0. 0, 0, 3-3] --> [0, 0, 0. 0]
For any rate K <4, he will require additional time. Therefore you will return 4

Sample input 1:
3
6 16 8 10

Sample output 1:
8

Sample input 2:
5
22
33 30 24 23 23

Sample output 2:
7

Sample input 3:
25
33
40 22 16 3 58 38 41 8 34 36 57 48 12 2

Sample output 3:
41

Sample input 4:
70
98
2 35 25 29 98 63 29 76 100 54 42 64 55 83

Sample output 4:
64

Question 3

Special Package

You are the manager of a grocery store and you want to create a special
package deal for your customers. You are given a matrix of prices of size
N * M for different products, with each row representing a different category
of products and each column representing a different product within that
category.
You want to select one item from each category such that the total cost of the
package is as close as possible to a specific target price K.
You need to determine the minimum absolute difference between the target
price and the total cost of the package you can create using the products in
the matrix.
Note: Exactly 1 item from each category has to be selected.
Function description
Complete the function solution() provided in the editor. The function takes the
following 4 parameters and returns the solution:

• N: Represents the number of categories
• M: Represents the number of items in each category
•K: Represents the target price
•price: Represents the price of items

Input format for custom testing
Note: Use this input format if you are testing against custom input or writing
code in a language where we don't provide boilerplate code
• The first line contains N denoting the number of categories.
• The second line contains M denoting the number of items in each category.
•The third line contains K denoting the target price.
• Each of the next N lines contains M integers each, denoting the price of the items.
Output format
Print an integer, representing the minimum absolute difference between the
target price and the total cost of the package.
Constraints
1 ≤N,M ≤ 70
1 ≤price[i][j]≤ 70
1 ≤ K ≤ 800

Sample input 1
3
1
100
1
2
3

Sample output 1
94

Sample input 2
1
5
42
9 33 35 70 39

Sample output 2
3

Explanation
Given
Input:
N= 3
M= 1
K = 100
price = [[1],[2],[3]]
Output: 94
Approach:

The best possible choice is to:
- Choose 1 from the first row.
- Choose 2 from the second row
- Choose 3 from the third row.
The sum of the chosen elements is 6. and the absolute difference is 94.

14 months ago

Systumm • 200

Mumbai

first problem Leetcode(881)  sorting+greedy

   int numRescueBoats(vector<int>& people, int limit) {

       sort(people.begin(),people.end());

           int i=0,j=people.size()-1,cnt=0;

        while(i<=j){

            if(people[i]+people[j]<=limit){

                i++;

                j--;

               // cnt++;//

            }else{

                j--;

            }

                cnt++;

        }

            return cnt;

    }

14 months ago

Systumm • 200

Mumbai

Q2.  Very popular BINARY SEARCH ON ANSWERS technique   LEETCODE(875) KOKO EATING BANANAS

take lo=1 hi=maxElemnt of array 

apply binary search  in which we take mid as rate(k) 

and check whether all coins can be melted with that rate in given time(H) 

if yes then ans=mid and decrease search space as hi=mid;

else lo=mid+1;

  int minEatingSpeed(vector<int>& piles, int h) {

        int left = 1;

        int right = 1000000000;

        while(left <= right){

            int mid = left + (right - left) / 2;

            if(canEatInTime(piles, mid, h)) right = mid - 1;

            else left = mid + 1;

        }

        return left;

    }

    bool canEatInTime(vector<int>& piles, int k, int h){

       long int hrs = 0;

        for(int pile : piles){

           long int div = pile / k;

            hrs += div;

            if(pile % k != 0) hrs++;

        }

        return hrs <= h;

    }