Scaler Topics Fortnightly Contest - 22 Editorial
FREE
DSA Fortnightly - 22 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 22
Rings with Prime Numbers
You are given a square matrix A of size N x N. Imagine this matrix as a set of concentric squares, with the outermost square forming the 1st ring, the second outermost square forming the 2nd ring, and so on. Your task is to count the number of prime numbers in each of these rings.
Problem Constraints
Input Format
- First argument is a 2D array A.
Output Format
- Return an array where A[i] contains count of prime numbers on the i-th ring of A.
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: 1st Ring has numbers: 1, 2, 3, 4 in which 2, and 3 are prime numbers.
Explanation 2: 1st Ring has numbers: 1, 2, 3, 4, 5, 6, 7, 8 in which 2, 3, 5, and 7 are prime numbers.
2nd Ring has the number 10 only and which is not a prime number.
Hint
- Try to use the sieve of Eratosthenes, to check whether a number is prime or not in an efficient way.
Complete Solution
Distribution of Gifts
Alice and Bob are organizing a charity event where they need to distribute N gifts among B groups of people. The gifts have different worth, represented by an array A of N non-negative integers.
Each group of people wants exactly two gifts of almost the same worth. In order to maximize the overall happiness of the people, Alice and Bob want to distribute the gifts such that the maximum difference between the worth of gifts received by any group is minimized.
You have to return the minimum of the maximum possible difference between the worth of gifts received by any group.
Problem Constraints
Input Format
- First argument is an array of integers A.
- Second argument is an integer B.
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: Gifts assigned to all 3 groups can be like [1, 2], [3, 4], and [5, 6] So, the maximum difference between the worth of gifts for any group is 1 as -
- 2 - 1 = 1
- 4 - 3 = 1
- 6 - 5 = 1
Therefore, the maximum between all of them is 1.
Explanation 2: Gifts assigned to both the groups can be like [1, 1], and [3, 5]. So, the maximum difference between the worth of gifts for any group is 2 as -
- 1 - 1 = 0
- 5 - 3 = 2
Therefore, the maximum between all of them is 2.
Hint
- Think about the binary search on 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
Minimize Randomness
You are given an array A1, A2, . . . , An , consisting of N integers. Lets define randomness of the array with respect to a number X as:
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 and only argument is a 1D integer array A.
Output Format
- Return the rounded value of 104 * X.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: With X = 3, the randomness for array A will be: (1-3)3 + (2-3)3 + (3-3)3 + (4-3)3 + (5-3)3 = 0. So value you should return => round(3 * 104) = 30000.
Explanation 2: Value of X for which randomness reaches 0 is 8.8674071988... that is when rounded and multiplied by 104 become 88674.
Turn Learning into Career Growth
Hint
- It can be proven that answer always exist and is unique.
- Is there any direct relation between randomness of array and value of X?
Complete Solution
Minimum Money Required
You are given two strings A and B having lengths N and M, respectively. You have to convert A to B. There are four possible actions you can perform on A, each requires some amount of money.
- Insert any character in A at any position.
- Choose i (0 <= i < N), delete A[i]. After deletion, string A[0 to i - 1] and A[i + 1 to N - 1] get concatenated (0-based indexing).
- Choose i and do A[i] = any character of your choice
- Choose i and j such that |i - j| = 1, and swap(A[i], A[j])
You are also given an integer array C having size 4 such that C[0], C[1], C[2], and C[3] is the money required to perform action 1, 2, 3, and 4, respectively.
Return the minimum money required to convert A to B.
Problem Constraints
A and B only contain lowercase English characters.
Input Format
- First argument is a string A
- Second argument is a string B
- Third argument is an array of integers C
Output Format
- Return an integer denoting the minimum money required to convert A to B.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Delete A[0] => Money required 1 Insert ‘d’ in the last of A => Money required 1. The total money required equals 2.
Explanation 2: Swap A[0] with A[1] => Money required 2 Replace A[2] with ‘d’ => Money required 1 The total money required equals 3.
Hint
- Try to think about using 2D DP to handle all the actions appropriately.
