Scaler
Academy
Data Science
AI/ML
DevOps
Neovarsity
AI FDE Program
IITR Degree Program
New
Skill Test
Search for Articles, Topics
Scaler Topics Fortnightly Contest - 26 Editorial

Scaler Topics Fortnightly Contest - 26 Editorial

Learn via video courses
Topics Covered

DSA Fortnightly - 26 Editorial

This article is part of the Scaler Topics Fortnightly Contest - 26

Make GCD

Given an array of integers A, you can perform the following operation any number of times - Select an element and add or subtract 1 from it. What is the minimum number of operations required to make the GCD of the array equal to B. Note that you can’t make an element negative.

Problem Constraints

2<=∣A∣<=1050<=∣A[i]∣<=1091<=B<=1000\begin{aligned} 2 <= |A| <= 10^5\\ 0 <= |A[i]| <= 10^9\\ 1 <= B <= 1000\\ \end{aligned}

Input Format

  • The first argument is an integer array A.
  • The second argument is an integer B.

Output Format

  • Return an integer, the minimum number of operations.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration
AI-LedCurriculum
Career SupportSupport
Program highlights
Go to Program
NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: We can change 5 to 4 in 1 operation and the GCD becomes 2.

Explanation 2: We can change 2 to 3 in a total of 1 operations to make the GCD equal to 3.

Hint

  • Try to find the nearest multiple of B.

Complete Solution

Make GCD Problem Complete Solution

Bead Challenge

You possess a vector A of size N, where Ai denotes the weight of the i-th bead among n beads on a table. Engaging in a competition against a machine, you have the liberty to select any two beads, keeping one for yourself (Ai) and surrendering the other to the machine (Aj). If you choose to retain Ai, you can partition its weight into k beads of equal weight (resulting in a new weight of Ai/k for the i-th bead). However, you must keep one of these new beads and discard the remaining k-1 beads. Subsequently, the machine will amplify the weight of the j-th bead (initially Aj) to k times its original weight (k*Aj). The objective is to achieve equal weights for all beads through a series of operations. Return 1 if successful or 0 if unsuccessful in this challenge.

Problem Constraints

2<=∣A∣<=1051<=Ai<=106\begin{aligned} 2 <= |A| <= 10^5\\ 1 <= Ai <= 10^6\\ \end{aligned}

Input Format

  • The first and only argument is array of integers A.
Sharpen Your Fundamentals with Free Learning

Output Format

  • Return 1 if you successfully achieve equal weights for all N beads; otherwise, return 0.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: We can never make all beads of equal size.

Explanation 2: Let's examine the vector A, which is [100, 2, 50, 10, 1], containing 5 elements. Two operations are performed on it:

Select a3 (which is 50) and a2 (which is 2), with k as 5. Replace a3 with a3 / k, resulting in 10, and replace a2 with a2 * k, resulting in 10. The modified array is now [100, 10, 10, 10, 1].

Choose a1 (which is 100) and a5 (which is 1), with k as 10. Replace a1 with a1 / k, resulting in 10, and replace a5 with a5 * k, resulting in 10. The final array is [10, 10, 10, 10, 10].

Hint

  • Try to think in divisors form.
  • Think of what could be done with constraints.

How Scaler Transformed Careers in Different Fields

₹23L
AVG CTC
SCALER PLACEMENT PROOF

Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.

11,000+placements
650+companies
Verified data
Hiring Partners:
GoogleGoogleAmazonAmazonMicrosoftMicrosoftFlipkartFlipkartAdobeAdobe1200+ more

Complete Solution

Bead Challenge Complete Solution

How many Divisions?

Given an array A of size N, divide it into non-empty subarrays such that every element is in exactly one of the subarrays. The value of such division is equal to ∑i⋅Sumi where i is the subarray number and ranges from 1 to K where K is the number of subarrays, and Sumi is the sum of the ith subarray. Among all possible divisions, you must get the maximum possible sum of values. How many such divisions are there where you can get such value? As the answer might be very large, return the answer modulo 1000000007.

Problem Constraints

1<=A<=105−109<=∣A[i]∣<=109\begin{aligned} 1 <= A <= 10^5\\ -10^9 <= |A[i]| <= 10^9\\ \end{aligned}

Input Format

  • The first argument is an integer array A.

Output Format

  • Return an integer, the answer modulo 109 + 7.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1: There is only 1 possible way to get the maximum sum. We need to divide it into 3 parts - [1], [0], [1]. The sum would be 1*(1) + 2*(0) + 3*(!) = 4.

Explanation 2: The total sum is going to be 0 no matter what. So, we can take all the possible divisions, i.e., {[0], [0]} and {[0, 0]}.

Turn Learning into Career Growth

1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary
1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary

Hint

  • At what points should we end a subarray? Can we think of a mathematical idea where we can tell if ending a subarray right now is alright or not.

Complete Solution

How many Divisions? Complete Solution

Rectangle Cutting

You need to form a rectangle X having an area of A units. You need to form X in such a way that you can carve out a rectangle with area B from it. The rectangles should have integral lengths and breadths. You need to find the minimum possible perimeter of X.

Problem Constraints

1<=A<=10131<=B<=A\begin{aligned} 1 <= A <= 10^{13}\\ 1 <= B <= A\\ \end{aligned}

Input Format

  • The first argument is a long integer A.
  • The second argument is a long integer B.

Output Format

  • Return a long integer, the minimum possible perimeter.

Example

Example Input Input 1:

Input 2:

Example Output Output 1:

Output 2:

Example Explanation Explanation 1:

The two possible ways for X are to have a length = 2 and a breadth = 2 or length = 4 and breadth = 1. In both cases, we can carve out a rectangle with dimension 2 X 1. Perimeter for 1st case = 2*(2+2) = 8 and for 2nd case = 2*(4+1) = 10. So, the answer is 8.

Explanation 2:

The two possible ways for X are to have a length = 4 and a breadth = 2 or length = 8 and breadth = 1. In both cases, we can carve out a rectangle with dimension 4 X 1. Perimeter for 1st case = 2*(4+2) = 12 and for 2nd case = 2*(8+1) = 18. So, the answer is 18.

Hint

  • Factorization of B and A can reduce the options of length.
  • Binary searching on factors of B for finding the best choice for a particular length of X.

Complete Solution

Rectangle Cutting Complete Solution