Scaler Topics Fortnightly Contest - 23 Editorial
FREE
DSA Fortnightly - 23 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 23
Count of Distinct Pairwise Sum - I
Given an array of integers A, your task is to find the number of distinct integers that can be obtained as the sum of any two integers chosen from array A.
For Example: Consider the array A = [1, 2, 1].
The possible unique sums of pairwise combinations from A are 1 + 1 = 2 and 1 + 2 = 3 and 2 + 1 = 3. Hence, the number of distinct integers possible as the sum of any two chosen integers from the array A is 2 (which are 2 and 3 in this case).
Problem Constraints
Input Format
- First and only argument is an array of integers A.
Output Format
- Return an integer denoting the required answer.
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: Explanation given in the problem statement.
Explanation 2: Only sum possible is 2.
Hint
- Use Nested loop along with a set to hold the distinct sums possible..
Complete Solution
Count of Distinct Pairwise Sum - II
Given an array of integers A, your task is to find the number of distinct integers that can be obtained as the sum of any two integers chosen from array A.
For Example: Consider the array A = [1, 2, 1].
The possible unique sums of pairwise combinations from A are 1 + 1 = 2 and 1 + 2 = 3 and 2 + 1 = 3. Hence, the number of distinct integers possible as the sum of any two chosen integers from the array A is 2 (which are 2 and 3 in this case).
Problem Constraints
Input Format
- First and only argument is an array of integers 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: The explanation is given in the problem statement.
Explanation 2: The only sum possible is 2.
Hint
- Create an array out of A which contains only distinct numbers, the size of this array can go up to 103.
- Now, you can do brute force & find the answer.
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
Minimum Total Travel Time
There is a land represented in the form of a matrix A having dimensions N x M where each of its cells denotes a unique city. Moreover, A[i][j] = 0 represents a city under construction and no one can travel through this city or visit this city, although apart from these kinds of cities every other city is constructed and denoted by A[i][j] = 1; one can travel through or visit these cities.
You and your two other friends initially are in cities B, C, and D.
Obviously, , and (0 - based indexing) which means any of you guys are not in an under-construction city.
You all three want to meet, so looking for a city such that the sum of travel time for all of you will be minimized. If they can’t meet then return -1.
Note:
- One can travel from a city to any adjacent city, meaning left, right, or up, down.
- Traveling from one city to another incurs 1 unit of time.
Determine the value of X at which the randomness of the array reaches 0. Return the rounded value of 104 * X.
Problem Constraints
Input Format
- First argument is a 2D array of integers A
- Second argument is an array of integers B
- Third argument is an array of integers C
- Fourth argument is an array of integers D
Output Format
- Return an integer denoting the minimum sum of the total time required by all of you to travel to the meeting city.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: The optimal meeting point is (1, 1). The total travel time for all of you will be 2.
Explanation 2: The only possible meeting point is A[0, 1] such that the minimum total travel time to this city is 2.
Turn Learning into Career Growth
Hint
- Think about using a traversal technique like BFS or DFS.
Complete Solution
Krishna’s Divine Partition
In the legendary saga of Mahabharata, guided by the divine wisdom of Lord Krishna, we encounter a mystical challenge. Imagine that Krishna revealed a sacred string A to the Pandavas, consisting of N digits. Each digit within the string ranges from 1 to 9. The significance lies in partitioning the string into substrings, ensuring that each substring, when interpreted as a decimal number, is strictly greater than the previous substring, symbolizing a divine strictly increasing order.
For instance, consider a sacred string "763569" with six digits. By partitioning it into three substrings: "7", "63", and "569", each representing strictly increasing decimal values, you embody the essence of Krishna's teachings.
Your task is to unravel the secret concealed within the sacred string. Determine the maximum number of partitions while preserving the divine order prescribed by Krishna.
Problem Constraints
A and B only contain lowercase English characters.
Input Format
- The first and only argument is a string A, of length N.
Output Format
- Return an Integer representing the maximum number of partitions as described.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Substrings formed: "7", "63", "569"
Explanation 2: Substrings formed: "2", "8", "34", "98", "3867"
Hint
- Carefully look at constraints of the problem, dynamic programming might help. But what will be the states?
