Scaler Topics Fortnightly Contest - 5 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 5.
Height Difference - II
There are N employees from 1 to N. The height of the ith employee is Ai. The manager wants to divide the employee into groups such that no two adjacent employees in a group have a height difference of more than B when the group is sorted. Furthermore, the manager can add at most C number of employees with arbitrary heights.
Help the manager find the minimum number of groups that he could form.
Problem Constraints
Input Format
- The first argument is an integer array A. Representing the height of the ith employee.
- The second argument is an integer B.
- The third argument is an integer C.
Output Format
- Return an integer representing the minimum number of groups that can be formed.
Transform Your Career
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
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Minimum of one group is required by adding an employee of height 4. {{2, 3, 4, 5}}
Explanation 2: Minimum of two groups are required. {{1, 1, 2, 3}, {11, 13}}
Hint
- Sort the employees by heights and make groups of adjacent employees, and add the employees greedly between the groups to get minimum number of groups.
Complete Solution
Minimize AND of XOR
You are given a matrix A of size N * M. Xority of a row A[i] is defined as A[i][0] ⊕ A[i][1] ⊕ ... ⊕ A[i][M]. Beauty(A) is defined as Xority(A[0]) & Xority(A[1]) & ... & Xority(A[N]).
You can apply the following operation up to B times:
- choose i (1 <= i <= N) and j (1 <= j <= M) and toggle a bit at any position of A[i][j].
Return the minimum Beauty(A) possible if you apply the operations optimally.
Problem Constraints
Input Format
- The first argument is matrix A and the second argument is B.
Output Format
- Return the minimum Beauty(A) possible if you apply the operations optimally.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1:
You can't apply any operation since B = 0. Hence, Beauty(A) = Xority(A[0]) & Xority(A[1]) = (1 ⊕ 1 ⊕ 1) & (1 ⊕ 3 ⊕ 3) = 1.
Explanation 2: You can flip the 0th bit of A[0][1] which will convert it into 2. This will achieve minimum Beauty(A) = Xority(A[0]) & Xority(A[1]) = (2) & (1) = 0.
Hint
- Think bit by bit. If we had a choice to only 1 operation and there are 2 high bits in current Beauty(A), what’d you do?
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Sherlock's Graph
Sherlock Holmes was yet again against Moriarty. Sherlock found out about Moriarty's latest plans.
Moriarty plans to kill people on a group of islands. He has bombs on each island, and detonating the bomb on one island would trigger a chain reaction and detonate all the islands connected to the original island directly or indirectly.
Dr. Watson gave Sherlock the map of the islands which is the form of a graph with A islands and M connections between the islands, and also the information of the population of each island.
Then, both of them were thinking how to reduce the number of people killed. So, Watson suggested to remove the connections. Now, Sherlock starts thinking about the various scenarios and he came up with Q questions in his mind.
The questions were of two types:
- 1 X Y : Remove a connection between island X and Y, (do not do anything if it does not exist).
- 2 0 0 : Find the maximum possible number of people that Moriarty could kill in one detonation. Sherlock suprsingly needs your help to complete this puzzle. Answer his questions.
Problem Constraints
Input Format
- The first argument is an integer A, denoting the number of islands.
- The second argument is an integer array B, denoting the number of people on each island. (ith index denotes the number of people on (i+1)th island)
- The third argument is a 2D integer array C, denoting the connections between the islands.
- The fourth argument is a 2D integer array D, denoting the questions by Sherlock.
Output Format
- Return an integer array consisting of the answers to the 2nd type of questions.
Example
Example Input Input 1:
Example Output Output 1:
Example Explanation Explanation 1: The given graph is:
1
|
2
/ \
3 - 4
\
5
We see all the islands are connected, so the answer is 15 for the first query. Then, we remove the connection between island 1 and 2, so the total number of people in connected islands are [1, 14]. The maximum is 14, so the answer is 14. Similiarly, after removing the connection between 4 and 5, the answer becomes 9. Now, even after removing the edge between 2 and 3, the answer is still 9 because the two islands are connected via 4.
Turn Learning into Career Growth
Hint
- What if we process the queries in a reverse order?
- Then, our queries would modify to connect an edge between X and Y, instead of removing an edge.
Complete Solution
Delivery Boy
Given a map of a connected city with A houses and A-1 roads. House 1 is the warehouse and you have to deliver C packages to C houses D[1], D[2], ..., D[C]. Find the shortest distance travelled by you to deliver these packages to these houses by visiting them at least once in any order. You begin from the warehouse. The ith road connects house B[i][0] and house B[i][1] and is of length B[i][2].
Problem Constraints
Input Format
- The first argument is a single integer A.
- The second argument is a 2D integer array B.
- The third argument is a single integer C.
- The fourth argument is an integer array D.
Output Format
- Return the shortest distance travelled by you to deliver these C packages to these houses by visiting them at least once in any order.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Visit nodes in the following order - 1 - 2 - 1 - 4 - 3.
Explanation 2: Visit nodes in the following order - 1 - 2 - 3 - 2 - 4 - 2 - 5.
Hint
- Note that we dont have to come back to the warehouse again once we visit the last package.
- Say if the problem was that we had to go back to the warehouse after delivering all packages can you solve the problem?
- Think if you can use that to solve the original problem.
