Scaler Topics Fortnightly Contest - 21 Editorial
FREE
DSA Fortnightly - 21 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 21
Itachi's Sacrifice
Our dear Itachi once again secretly is trying to save Sasuke. Itachi needs to stop the reanimation jutsu in order to save the shinobi world and the Hidden Leaf village.
Itachi is given an array A of size N consisting of 0s and 1s. Itachi needs to convert all the elements into 1 in order to stop this jutsu.
Itachi's genjutsu works in the following way. He first needs to fix and stand at some position x in the array where 1 < x < N. Itachi won't be able to change the value of this index. However, he can choose some elements from the left of this index and some from the right and change the parity of both these values. Suppose he selects index l from the left and index r from the right then he does A[l] ^= 1 and A[r] ^= 1 simultaneously.
Itachi can perform this operation any number of times.
Return 1 if Itachi can ever break reanimation jutsu, else return 0.
Problem Constraints
Input Format
- First and only argument contains A.
Output Format
- Return a single integer denoting the required 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: Itachi can stand at 2nd index , and in one move he can change both 1st and 3rd index values to 1.
Explanation 2: There is no way where Itachi can convert all the elements to 1.
Hint
- Notice how the flipping move works. Notice all the transitions you can make. There are 4 ways you can select values from left and right. {1,0}, {1,1}, {0,1}, {0,0}. Can you observe the common thing in all the transitions?.
- The parity of 0s always remains same.
Complete Solution
Suspicious Bank
There is one suspicious bank in your city. This bank can hold only Rs. A at a time. Initially, the bank has Rs. A and now the process begins.
- At the start of each day Rs. B is deposited in the bank. But the limit should not exceed A, if it does then the extra money is not deposited and is considered waste.
- At the end of each day Rs i, is withdrawn from the bank, where i is the number of that day starting from 1 (i.e 1, 2, 3 ...). If the bank has less than Rs i. then only the amount the bank has is withdrawn. So, you have to find the first day when the bank has Rs. 0 at the end of the day.
Return an integer which denotes the day number at which the bank has Rs. 0 at the end of the day.
Note - We started from day 1 and at the start of day 1, the bank has Rs. A.
Problem Constraints
Input Format
- The first argument is an integer 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: At the beginning of day 1 there were Rs. 4 in the bank.
- Day 1 - After Deposit - Rs. 4 (as the amount can't exceed A, 4+5 = 9) After Withdrawn - Rs. (4 - 1) = Rs. 3
- Day 2 - After Deposit - Rs. 4 (as the amount can't exceed A, 3+5 = 8) After Withdrawn - Rs. (4 - 2) = Rs. 2
- Day 3 - After Deposit - Rs. 4 (as the amount can't exceed A, 2+5 = 7) After Withdrawn - Rs. (4 - 3) = Rs. 1
- Day 4 - After Deposit - Rs. 4 (as the amount can't exceed A, 1+5 = 6) After Withdrawn - Rs. (4 - 4) = Rs. 0 So, the answer will be 4.
Explanation 2: At the beginning of day 1 there were Rs. 5 in the bank.
- Day 1 - After Deposit - Rs. 5 (as the amount can't exceed A, 5+2 = 7) After Withdrawn - Rs. (5 - 1) = Rs. 4
- Day 2 - After Deposit - Rs. 5 (as the amount can't exceed A, 4+2 = 6) After Withdrawn - Rs. (5 - 2) = Rs. 3
- Day 3 - After Deposit - Rs. 5 (3+2 = 5) After Withdrawn - Rs. (5 - 3) = Rs. 2
- Day 4 - After Deposit - Rs. 4 (2+2 = 4) After Withdrawn - Rs. (4 - 4) = Rs. 0 So, the answer will be 4.
Hint
- There might be some process how the amount in the bank changes.
- What would be the answer if A<=B?
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
Minimum Product
Given an array of integers, A. Find how many quadruples of indices (i, j, k, l) (i < j < k < l), such that A[i] * A[j] * A[k] * A[l] is minimum possible.
Return the number of such quadruples possible mod 998244353.
Note: You don't have to return the minimum product possible.
Problem Constraints
Input Format
- The first argument is an interger array A.
Output Format
- Return an integer denoting the required answer.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1:
- Minimum Product for any quadruple if array A is 3 * 4 * 5 * 10 = 600
- There are two possible quadruple indices [0, 2, 3, 4] and [1, 2, 3, 4]
Explanation 2:
- Minimum Product for any quadruple if array A is 5 * 6 * 5 * 6 = 900
- There are one possible quadruple indices [0, 1, 2, 3]
Turn Learning into Career Growth
Hint
- There are multiple cases which we have to take care off.
- We are only concerned of frequency of four smallest numbers of the array.
Complete Solution
Gang of Thieves
Ekansh, a skilled detective, was hot on the trail of a notorious gang of thieves carrying out a series of daring robberies in a city. The gang had managed to evade capture, and the city was in turmoil. Ekansh had received intelligence that the gang's hideout was located in one of the districts within the city.
The city was divided into N districts, each with its own unique characteristics, interconnected by a network of bidirectional roads. Moreover, it is possible to reach any district from any other one by traversing through one or several roads.
Ekansh had also learned that districts within a distance of B or less from the hideout were under the influence of the gang's robberies.
Ekansh had identified C districts already known to be affected by the gang's robberies. However, there could be other districts that were also being targeted by the gang, but their plight had not yet been discovered.
Ekansh was determined to bring the gang to justice and put an end to their criminal activities. He sought your assistance in solving this challenging puzzle.
You are given the layout of the city in the form of a 2D array A which has (N - 1) rows and 2 columns such that A[i][0] and A[i][1] denote the districts having bidirectional road between them.
You have to return an integer denoting the number of possible hideouts or the districts in which the gang may be hidden, it may be possible that the intelligence received by Ekansh is incorrect and there is no district where Gang can be there, in that case, return 0.
Problem Constraints
Input Format
- First argument is a 2D array of integers A.
- Second argument is an integer B.
- Third argument is an array of integers C.
Output Format
- Return an integer denoting the required answer.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Already affected district = 1 Districts up to 1 distance from the hideout may be affected. Therefore possible hideout of the Gang could be in districts 1, 2, and 3.
Explanation 2: Already affected district = 1 Districts up to 2 distances from the hideout may be affected. Therefore possible hideout of the Gang could be in districts 1, 2, 3, and 4.
Hint
- Try to think of using DFS traversal multiple times to reach the deepest affected district.
