Scaler Topics Fortnightly Contest - 17 Editorial
FREE
DSA Fortnightly - 17 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 17
Optimal Subarray selection
Given an array A of N integers and an array B of Q queries. Each query consists of two integers B[i][0], B[i][1] and you have to determine the sum of the maximum sum subarray among all the subarrays [x, y] such that x is lesser or equal to B[i][0] and y is greater or equal to B[i][1].
Note: [x, y] denotes the subarray starting at index x and ending at index y.
Problem Constraints
Input Format
- The first argument is the array A and the second argument B is the array of queries.
Output Format
- Return a list of integers.
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: For the first query the maximum sum subarryay is [1, 4]. For the second query the maximum sum subarray is [2, 4].
Explanation 2: For the first query the maximum sum subarryay is [1, 4]. For the second query the maximum sum subarray is [1, 5].
Hint
- We can solve this problem with the pefix sum and it's maxima and minima computation.
Complete Solution
Swap Sort
You are given an array A of N integers. In one operation, you can swap any two adjacent integers of A such that the integers have different counts of digits. You will have to find if it's possible to sort the array by performing any number of operations
Problem Constraints
Input Format
- Only argument A is an array of integers
Output Format
- Return 1 if its possible to sort the array and 0 if its not possible.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: In the first operation we can swap the second and third element of the array, A becomes [10, 5, 18]. In the next operation, we can swap the first two elements. Thus A becomes [5, 10, 18]. Hence, we are able to sort this array.
Explanation 2: We would never be able to sort the given array. So, we return 0.
Hint
- We would never be able to change the relative ordering of the elements with the same number of digits.
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
Powerball Tournament
Scaler is going to organize a powerball tournament. In the tournament there are A types of powerballs. All the candidates will get exactly N powerballs. Array B of size N, denotes the type of the powerball and array C of size N, denotes the strength of the powerball(which can be negative as well).
Rules of tournament are:
- All the candidates have to choose some subset out of A types of powerballs.
- Number of powerballs of each type in the chosen subset should be same.
- Candidates with maximum non negative total strength of the powerball will win the tournament.
You being one of the candidate of the tournament have to the maximize the total strength of the powerball. Return the maximum possible total strength of the powerball.
Problem Constraints
Input Format
- The first argument given is an integer, A.
- The second argument given is an array, B.
- The third argument given is an array, C.
Output Format
- Return an integer denoting the maximum possible total strength of the powerball.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: It is optimal to choose 1st, 2nd, 3rd, and 4th powerball. So there are 2 powerballs of 2nd-type and 2 powerballs of 3rd-type. Total strength - 6+6+5+5 = 22.
Explanation 2: It is impossible to obtain a non-negative sum using any set of powerballs.
Turn Learning into Career Growth
Hint
- It is always optimal to take powerball with max strength for a fixed type.
- If we fix the number of powerballs for each type, then it is always optimal to take all powerballs with positive sum.
Complete Solution
Aesthetic food
Ramya is hosting a dinner night for her guests. She has invited A guests to her place for the dinner. She has N boxes of spices using which she will prepare the food(N>=A). Spices in her kitchen are present in an array of boxes, B and she will use a continuous segment of spices to prepare the food of a single guest. For every guest she will use atleast one box of spice to prepare the food, and each box of spices can be used to prepare the food for exactly one guest.
Aesthetic value of the food is defined by the variety of spices used to prepare the food, Formally, no of distinct spices used to prepare the food is its aesthetic value. Help her determine the maximum possible total Aesthetic value of her prepared dishes.
Problem Constraints
Input Format
- The first argument given is an integer, A.
- The second argument given is an array, B.
Output Format
- Return an integer denoting the maximum possible total Aesthetic value of her prepared dishes.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Since there is only one guest coming to her house, it will be optimal to use all 4 spices to prepare food. Since there are 2 distinct spices so answer is 2.
Explanation 2: It will be optimal to use first 2 spices for the first guest and rest all spices for second guest. Aesthetic value of food for guest 1 = 2 Aesthetic value of food for guest 2 = 3 Total Aesthetic value = 2+3 = 5.
Hint
Try to think of a dynamic programming approach:
- DP[i][j] - maximum aesthetic value that we can acheive by using first i spices for preparing j dishes.
- For j = 1: the answer is equal to the number of distinct values on a prefix(i).
- For j > 1: the answer can be deduced as follows (here c(x,i) denotes the number of distinct elements in range (x,i)): DP(i, j) = max 1<=x<i(dp(x-1, j-1)+c(x,i)).
