Scaler Topics Fortnightly Contest - 5 Editorial

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.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

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

Height Difference - II 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?

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complete Solution

Minimize AND of XOR Complete 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.

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

Sherlock's Graph 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.

Complete Solution

Delivery Boy Complete Solution