Scaler Topics Fortnightly Contest - 18 Editorial
FREE
DSA Fortnightly - 18 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 18
Months Cycle
You are given an integer array A, which denotes the days of different months.Months are consecutive. If a year is a leap year then the February month has 29 days except 28. And all the days in a month are the same as the real calendar. If the array represents the months of consecutive years then return 1 else return 0.
Problem Constraints
Input Format
- The first argument is an integer array A.
Output Format
- Return an integer
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: Months are December, January and February. The february month was not of leap year.
Explanation 2: Months are January ,February, March and April. This is a leap year. But april has 30 days. So, it should be [31, 29, 31, 30]
Hint
- In a calender there are 31 days in January,
- 28 or 29 days in February (depending on whether the year is leap or not),
- 31 days in March, 30 days in April, 31 days in May, 30 in June, 31 in July,
- 31 in August, 30 in September, 31 in October, 30 in November, 31 in December.
Complete Solution
Nearest similar number
You are given an integer A. Your task is to find an integer X, such that:
- Number of prime factors in the prime factorization of A and X are the same.
- Prime factorization of A and X differs by exactly one prime factor. For ex: if A = 12 (223), then possible value of X can be 18 (323), 30(253), 20(225) etc.
Among all possible values of X, return the one which has minimum possible value of abs(A-X). If there are multiple values of X possible, return the largest one.
Problem Constraints
Input Format
- The first and only argument given is the integer A.
Output Format
- Return an integer X
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Prime Factorisation of 12 = 223. If we change one 2->3, we get 233 = 18, and abs(18-12) = 6. But if we change one 3->2, we get 222 = 8, and abs(12-8) = 4, which is the minimum we can acheive.
Explanation 2: Prime factorisation of 36 = 2233. We get minimum value of abs(N-X) by changing 3->2, so X = 2223 = 24.
Hint
- Try to think of brute force approach.
- Since the value of N is only upto 1e5, we can generate all the prime factors of it.
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
Chocolate Boxes
There are N types of chocolates. Given an array A where A[i] is the number of chocolates of ith type. You have B boxes. One box can carry an infinite number of chocolates of one type. You have to find a way to put all the chocolates in the boxes such that the chocolates in the box with the maximum number of chocolates is minimum. Return the number of chocolates in the box with the maximum number of chocolates.
Problem Constraints
Input Format
- The first argument is an integer array A.
- The second argument is a single integer B.
Output Format
- Return the number of chocolates in the box with the maximum number of chocolates.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Box 1 has 3 chocolates of type 1 Box 2 has 12 chocolates of type 2 Box 3 has 12 chocolates of type 2 Box 4 has 8 chocolates of type 3
Explanation 2: Box 1 has 29 chocolates of type 1 Box 2 has 19 chocolates of type 2 Box 3 has 22 chocolates of type 3 Box 4 has 13 chocolates of type 4 Box 5 has 17 chocolates of type 5 Box 6 has 15 chocolates of type 6 Box 7 has 15 chocolates of type 6 Box 8 has 15 chocolates of type 7 Box 9 has 15 chocolates of type 8 Box 10 has 14 chocolates of type 8
Turn Learning into Career Growth
Hint
- If there are x boxes allocated for a specific chocolate type it is optimal to distribute the chocolates evenly in these boxes. So the max chocolate in a box will be ceil(A[i] / x).
- Try to think greedily. First assign 1 box to each chocolate type.
- Now try to think which type of chocolate should get one new box and come up with an algorithm.
Complete Solution
Pseudo Primes
A number is a Pseudo Prime if the sum of its distinct prime factors is also a prime number. Return the number of Psuedo primes in the range A to B.
Problem Constraints
Input Format
- The first argument is a single integer A.
- The second argument is a single integer B.
Output Format
- Return the number of Pseudo primes in the range A to B.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: The Pseudo Primes are 2, 3, 4, 5, 6, 7, 8, 9, 10. Sum of their distinct prime factors are 2 = 2 3 = 3 4 = 2 5 = 5 6 = 5 7 = 7 8 = 2 9 = 3 10 = 7
Explanation 2: There are 24 Pseudo primes in the given range.
Hint
- The naive approach will be to iterate over all the numbers.
- Find their prime factors sum them and check if the sum is prime.
- But this is too slow as iterating over the range is O(N) and then prime factorisation is O(sqrt(N)) and then checking
- if the sum is prime is another O(sqrt(N)).
- Overall time complexity is O(N sqrt(N)) which is slow for the given constraints.
- Try to use Sieve of Eratosthenis.
