Scaler Topics Fortnightly Contest - 24 Editorial
FREE
DSA Fortnightly - 24 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 24
The Upside Down
Mike and the company from Stranger Things are given a map of Hawkins represented by a matrix A having R rows and C columns. The map has some portals on some of the cells that they can take to go the Upside-Down and can come back to the main city through another one of these portals. A cell (i,j) has a portal if A[i][j] = 1 and otherwise A[i][j] = 0. If they have a portal on a cell, they may not take it.
They can only travel in four directions, Up, Down, Left, and Right. The time taken to travel to any of the neighboring cells in one of these directions is 2 units. The time taken to do the same in the Upside-Down is 1 unit. If they start from the upper left corner of the map and have to reach the bottom right corner of the map, what is the minimum time taken by them to do so?
Note: Note that they have to reach the right corner in the main city, not the Upside-Down. They may use the portal an infinite number of times but the use should be an even number as they don’t want to be in the Upside-Down in the last. Passing through the portal takes 0 units of time.
Problem Constraints
Input Format
- The first argument is an array of array of integers A.
Output Format
- Return an integer denoting the answer.
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: There is only one way to go to the bottom right corner and it takes 2 units of time.
-
Explanation 2: We can go to the right, then we can pass through the portal and go down. It takes a total of 2 + 1 units of time.
Hint
- Effectively how many portals are going to be used?
Complete Solution
Spaceship on Mission
There are many planets in the universe represented as P(i, j) where (i, j) is the location of the planet. Two planets P1(i1, j1) and P2(i2, j2) are called neighbouring if |i1 - i2| + |j1 - j2| = 1.
There is a spaceship at planet P1(A[0], A[1]). The spaceship can only travel to neighbouring planets taking 1 unit of time. The spaceship has a mission to destroy the planet P2(A[2], A[3]). Once the spaceship destroys the planet P2, it creates a portal P2 and it makes the spaceship teleport to the another portal at planet P3(A[4], A[5]). The spaceship needs to return to its planet P1. The spaceship needs to complete the mission in the shortest time possible. Completion of the mission means destroying the planet P2 and coming back to the planet P1.
What is the maximum number of planets that the spaceship can visit twice while completing the mission. A is an array of size 6 which represents the location of the planets.
Problem Constraints
Input Format
- The first and only argument is array of integers A.
Output Format
- Return the maximum number of cells that both robots can traverse together if they each follow their respective shortest paths home.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
-
Explanation 1: The spaceship can take the path as (3, 1), (3, 2), (3, 3), (2, 3), (1, 3). It then teleports to (6, 4). The returning path would be (6, 4), (6, 3), (5, 3), (4, 3), (3, 3), (3, 2), (3, 1). It visits the planets (3, 1), (3, 2) and (3, 3) twice. So, the answer is 3.
-
Explanation 2: The path taken would be (5, 2), (4, 2), (3, 2), (2, 2). The returning path would be (7, 2), (6, 2), (5, 2). The only planet to be visited twice is (5, 2). So, the answer is 1.
Hint
- See that if a formula can be created to solve in O(1).
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
Subtracking
Given an array A of positive integers of length N, you can perform the following operation -
- Select two indexes i and j where 1 <= i < j <= N, and change them to |A[i] - A[j]| and min(A[i], A[j]) respectively.
- Find the minimum number of moves to make all the elements of the array equal.
Problem Constraints
Input Format
- The first argument is an integer array A.
Output Format
- Return an integer, the minimum moves to make the elements equal.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
-
Explanation 1: We choose the indices 2 and 3. The new numbers are |2-4| and min(2,4) which are 2 and 2 respectively. So, the array changes to [2, 2, 2] where all are equal. So, the minimum moves are 1.
-
Explanation 2: 0 moves are required as only 1 element is there.
Turn Learning into Career Growth
Hint
- Try to think of a greedy algorithm.
Complete Solution
Mario's Divisibility Dilemma
In Mario's world, a new challenge emerges. Mario encounters an array A of length N, containing only zeros and ones. These elements represent boxes that initially hold either a single chocolate or are left empty. You step in to help Mario tackle this intriguing puzzle, where you can shift a chocolate from a non-empty box to its neighboring box in one move.
The task is to determine the minimum number of moves required so that there exists an integer 'k' greater than 1, for which the number of chocolates in each box is divisible by 'k'. If there is no way to solve the puzzle, return -1.
Problem Constraints
Input Format
- The first and the only argument is an integer array A.
Output Format
- Return an integer representing the answer.
Example
Example Input
Input 1:
Input 2:
Example Output
Output 1:
Output 2:
Example Explanation
-
Explanation 1: In two moves we can transfer the chocolates from corner boxes to the middle box, ending up with [0, 2, 0], for which k = 2 satisfies the condition. It is not possible to do in less than 2 moves.
-
Explanation 2: As there is only one chocolate , we cannot have any K > 1, satisfying the condition. Thus, the answer will be -1.
Hint
- If any such k exists, then it will definitely be a divisor of the total number of chocolates in all boxes.
