Scaler Topics Fortnightly Contest - 11 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 11
Longest Mex Subarray
You are given an array A of size N. All the elements of the array are distinct. A subarray of length K (K<N) is called a good subarray if the MEX of the subarray equals to K. What is the maximum length of a good subarray? MEX is defined as the smallest non-negative integer not present in an array.
Problem Constraints
Input Format
- First argument A is an array of integer.
Output Format
- Return a single integer.
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: The longest good subarray is [3, 0, 2, 1].
Explanation 2: The longest good subarray is [0, 2, 1].
Hint
- Every integer from 0 to N-1 occurs only once in A. Can we use this information?
Complete Solution
Teacher and queries
There are several students who are asking queries to N teachers. Each query has a query_id assign to it.
Each teacher will answer exactly M distinct queries, but one query can be answered multiple times.
For each N teacher, you are given M pairs denoting the query_id and query_count(number of times query asked).
Your task is to find top K query_id which is asked maximum number of times across all teachers. If two queries are asked same number of times, query with largest query_id will be considered first.
Problem Constraints
Input Format
- First line consist of three space-separated integers N, M and K.
- Each of the next N lines contains 2*M space-separated integers denoting the M distinct queries, for each query, given query_id and query_count.
Output Format
- Print top K space-separated queryid in decreasing order of querycount.
- Note : After each query_id, there should be exactly one space.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: N = 3, M = 3, K = 4
Total count of each query_id: (3, 13), (7, 10), (10, 5), (2, 5), (6, 4), (1, 3). Top 4 is printed.
Explanation 2: N = 2, M = 2, K = 1
Total count of each query_id: (5, 10), (2, 10), (1, 1). Top 1 is printed i.e 5.
Hint
-
Firstly, sum all the query_count for each query_id using a hashmap.
-
Then, sort it in descending order of query_count.
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
Mysterious Treasure Hunt
You and your friends found a mysterious treasure map while playing in your backyard. All of you are very interested in treasure hunts. But this time it was dangerous. You had to cross the harsh seas and deserts of Arabia to reach the entry cave of the treasure map. After hours of walking in the cave avoiding many deadly traps, you reach the most difficult level on the map. As you try to open the gates of the treasure room a bad genie comes from nowhere. He asks you to play a game.
All A people (you and your friends) needs to stand on a game board that has B consecutive cells. One cell can be occupied by at most one person. Initial positions of all people are given by the genie by array C. If C[i] = 1 then a person is present in that cell else if C[i] = 0 the cell is empty. Length of C is B.
Now the game has two types of moves:- Say i j k are three consecutive cells in the board.
Move type 1 - If cell i is empty and cell j and k has a person each then person on cell k comes to cell i and the person on cell j is removed from the game.
Move type 2 - If cell k is empty and cell i and j has a person each then person on cell i comes to cell k and person on cell j is removed from the game.
The game stops when no more moves are possible.
Now the challenge is you have to end the game with the minimum number of possible people on the board. If you fail to do so you can move forward but the people who remained on the game board will die. If you succeed all people get into the room and keep their lives. Can you calculate and find the best way such that the minimum number of people remains in the end.
Return the minimum number of people that can remain on the board.
As soon as you solved the problem your mother called you up. You woke up and said "WHAT A WEIRD DREAM!"
Problem Constraints
Input Format
- The first input is a single integer A.
- The second input is a single integer B.
- The third input is an integer array C.
Output Format
- Return the minimum number of people that can remain on the board.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Initially [1, 1, 1, 0] After step 1 that is person at cell 2 jumps person at cell 3 and moves to cell 4, person on cell 3 is removed from game. [1, 0, 0, 1]
Explanation 2: Initially [1, 1, 1, 0, 1, 0] After step 1, [1, 0, 0, 1, 1, 0] After step 2, [1, 0, 1, 0, 0, 0]
Turn Learning into Career Growth
Hint
- Assume the given array C is a binary number. Now see that the constraints are just upto 24.
- So try to come up with an idea using bitmasking and memoization.
Complete Solution
Perfect Graph
You have been given an undirected connected weighted graph G consisting of A vertices and M edges, and a vertex B in the graph. You have to find the Perfect Graph of the given graph.
A Perfect Graph of the given Graph is an undirected weighted Tree T which has following properties:
It consists of all the A vertices of the graph. It consists of exactly A-1 edges out of the given M edges.
Distance of all the A vertices of the Tree from the vertex B, is smallest possible. Total weight of all the edges of the tree is minimum possible.
You are given three arrays, C, D, and E, each of size M, which represent that there is a bidirectional edge connecting vertex C[i] to D[i], and the weight of edge is E[i].
Return the sum of weight of all the edges of Perfect Graph.
Problem Constraints
Input Format
- The first argument is an integer array, A.
- The second argument is an integer array, B.
- The third argument is an integer array, C.
- The fourth argument is an integer array, D.
- The fifth argument is an integer, E.
Output Format
- Return an integer, denoting the sum of weight of all the edges of the Perfect Graph.
Example
Example Input Input 1:
Example Output Output 1:
Example Explanation Explanation 1: In this Tree formed by edges 2-3, 3-4 and 4-1 will form the Perfect Graph with total weight of edges 1+1+2 = 4.
We can also see that distance of all the vertices from 4(B) is minimum possible.
Hint
- Try to think of some Dijkstra modification, and how we can use it to find the weight of the sum of the weight of the perfect graph.
