Scaler Topics Fortnightly Contest - 19 Editorial
FREE
DSA Fortnightly - 19 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 19
Software features
You are developing a software with N members in your team, named as Member 1 through N. There are 2 features to be implemented, called Feature A and Feature B. Member i can implement feature A in A[i] hours and feature B in B[i] hours.
Your task is to assign each feature to one member, you can also assign both features to the same member, in which case the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually. If you assign them to different members, the time it takes for them to complete is the longer of the times it takes for them to do their respective works.
Find the shortest possible time needed to implement both features(in hours).
Problem Constraints
Input Format
- First argument is array A of size N
- Second argument is array B of size N
Output Format
- Return an integer specifying minimum number of hours required
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreExample
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: 3rd Member can do both implementation in minimum of 8 hours
Explanation 2: Assign A to 2nd member and B to 1st member, so minimum time is max(6, 7)
Hint
- Time complexity is not that much so we can solve it in O(N2)
Complete Solution
Minimum Cost
You are given an array A of integers, which represents the cost of each chocolate. Now, you have to buy all of the chocolates. But it's not easy to find the minimum cost to buy all chocolates. You are also given another array B which represents the type of offers in the chocolates. Each element of array B represents the number of chocolate you must buy to get at most 2 chocolates free of your choice.
Like it's your choice to select any of the offers each time and then you have to select that much chocolate from array A and you will get at most 2 chocolates on that free like if you have selected an offer of 3. Now, you have to select any three different chocolates assuming X, Y and Z. You can get at most 2 free chocolates of your choice on these 3 with a condition that the minimum cost of X, Y and Z is not smaller than the maximum cost of free chocolates taken. And it's your choice to take 0, 1 or 2 chocolates free.
Return the minimum amount you have to spend to buy all chocolates.
Note - You can buy any chocolate without using any offer also.
Problem Constraints
Input Format
- The first argument is an integer array A.
- The second argument is an integer array B.
Output Format
- Return an integer
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: You have only one offer. So, you can buy the first chocolate and take second and third as free. So, total cost will be 3.
Explanation 2: There are two possible cases, both of them will give same result. Case 1 - You can take first offer and buy first 3 chocolates and take last 2 as free. Total cost will be 30. Case 2 - You can take second offer and buy first 2 chocolates and take third and fourth chocolates as free. And at last take the last chocolate without any offer. Total cost will be 20+10 = 30.
Hint
- It is obvious that most optimal way is to use discount with minimum value.
- We can sort the array A.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Placement of Bots
There are N Bots to be placed on a number line. Each bot must be placed such that its position is between A[i] and B[i]. For position p of the ith bot, A[i] <= p <= B[i], p must be an integer and no other bots can be placed here. State whether it is possible to place all bots in their given range.
Problem Constraints
Input Format
- First argument is array A of length N
- Second argument is array B of length N
Output Format
- Return a boolean value stating possibility of placement of bots. 0 represents false and 1 represents true
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: There is no way we can place last bot in range [4, 5] as 4 and 5 have already been filled, so answer is 0
Explanation 2: One possible positions of bots can be 14, 2, 9, 20, 19
Turn Learning into Career Growth
Hint
- Try to think using binary Search because bruteforce solution won't pass the testcases
Complete Solution
Play with friend
You are playing with your friend. You have an integer array A and an integer B. Now, in each turn, you/your friend can subtract 1 from any element if it is positive or replace any even element x with B elements of x/2 value each. Now, this will go on until array A has any element left. And the one who performs the last move will win.
You are starting with the first move, if you win return 1 else 0.
Note:- Element will be automatically removed from the array if it becomes 0.
Problem Constraints
Input Format
- The first argument is an integer array A.
- The second argument is an integer B.
Output Format
- Return an integer.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
Explanation 1: Your move is first, in that move you will subtract 1 from 1st element.
Explanation 2: There is no even element in A. In first move you will subtract 1 from 1. Now, A = [1, 1] In second move your friend will subtract 1 from 1. Now, A = [1] In third move you will subtract 1 from 1. Now, A = []
Hint
- Is there a way to determine the winner of a game with many elements but looking at only one element at a time?
