Scaler Topics Fortnightly Contest - 7 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 7.
Make them Equal
You are given an integer array A and an integer B. In one operation, you can pick any element of A and subtract B from it i.e put A[i] := A[i] - B. Return the minimum number of operations required to make array A equal or -1 if it is impossible.
Problem Constraints
Input Format
- The first argument is an integer array A and the second and last argument is an integer B.
Output Format
- Return an integer denoting the minimum number of operations required to make the array A equal or -1 if it is impossible.
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: The array is already equal.
Explanation 2: We can subtract B from A[2] in 1 operation which would make the array equal.
Hint
- If we can make the array equal, what will be the final equal element? When can’t we make the array equal?
Complete Solution
Distribute Chocolates
You have A chocolates and you wants to distribute it to your C friends. Chocolates are represented by an array B, where Bi represents the length of the ith chocolate. You can break any chocolate into any number of pieces such that after breaking each piece has an integer length. You want to distribute chocolates as equally as possible, hence you want to minimize the maximum length of chocolate given to any of the C friends. Return this minimum length of maximum chocolate piece. If the chocolates can't be distributed among all your C friends returm -1.
NOTE: You cannot waste any chocolate piece i.e., the total number of pieces of chocolate at the end should be C.
Problem Constraints
Input Format
- First argument A is the number of chocolates.
- Second argument B is the array representing length of each chocolate.
- Third argument C is the number of friends.
Output Format
- Return a single integer representing the minimum length of maximum chocolate piece. Return -1, if chocolates can't be distributed.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: If is not possible to create a 6th piece by breaking any of the chocolates. Hence we cannot distribute the chocolates among all C friends.
Explanation 2:
Consider 1-based indexing: Break 3rd chocolate into length of 1 each. Break 5th chocolate into length of 1 and 2. Minimum length of maximum chocolate piece is 2. We can prove that this is the minimum length of any chocolate piece possible.
Hint
- We observe that the given solution is monotonic in the sense that if chocolates can be distributed with a particular length, then it can also be distributed with length less than that particular length.
- We can be use binary search to search for the right 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
Bitlandian Army
There is an army of N soldiers in Bitland. Each soldier has a strength and fierceness value associated with him given by arrays A and B of size N. You are the commander in chief, and your task is to form a battalion of soldiers with total strength at most C.
Cumulative strength of K soldiers is given by bitwise OR of strength values of all the K soldiers, i.e. Total strength = A1 | A2 | A3| … |Ak.
Cumulative fierceness of K soldiers is given by the summation of all the fierceness values of all the K soldiers, i.e. Total fierceness = B1 + B2 + B3 + …+ Bk.
You have to output the maximum possible fierceness value among all such possible battalions of soldiers.
Problem Constraints
Input Format
- The first argument given is the integer array, A.
- The second argument given is the integer array, B.
- The Third argument given is an integer, C.
Output Format
- Return an integer denoting the maximum possible fierceness value of a battalion.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: We will select A[0],A[1],A[2] and A[3], therefore A[0]|A[1]|A[2]|A[3] = 11 < 12. So the maximum sum of fierceness is 10 + 15 + 9 + 12 = 46.
Explanation 1: We will select A[0] and A[1], therefore A[0]|A[1] = 11 <= 11. So the maximum sum of fierceness is 10 + 14 = 24.
Turn Learning into Career Growth
Hint
- We say an integer A contains an integer B, if for each k such that A doesn’t contain the k-th bit, B also doesn’t contain the k-th bit.
Complete Solution
Building the Bridge
You have to build a bridge of length N, from pos 1 to pos N. There are three types of cost associated with building a bridge of length 1 at ith position: If there is no bridge adjacent to the ith pos, neither to its left nor to its right: A[i]. If there is exactly 1 bridge adjacent to the ith pos, either to its left or to its right: B[i]. If there are two bridges adjacent to ith pos: C[i]. What will be the minimum total cost required to build this bridge?
Problem Constraints
Input Format
- The first argument is array A.
- The Second argument is array B.
- The Third argument is array C.
Output Format
- Return an integer, denoting the minimum possible total cost to build the bridge.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Minimum total cost to build the bridge will be incurred when we build the bridges in following order: 1) i=4 , cost = 2 2) i=5 , cost = 2 3) i=3 , cost = 7 4) i=2 , cost = 4 5) i=1 , cost = 0 Total cost incurred will be: 2+2+7+4+0 = 15, which can be checked is minimum.
Hint
- cost of building the ith bridge, depends only on its adjacent bridges. If we build the (i-1)th bridge after building the ith bridge, then solution from (i+1)th to Nth bridge, does not depend on (i-1)th bridge.
- Try to come up with some dynamic programming states using this.
