DevuAndEqualizingLCM
SRM 814 · 2021-09-28 · by praveen123
Problem Statement
Devu has two arrays A and B. All elements of these arrays are positive integers.
Devu wants to have two arrays that have the same LCM (least common multiple) of all their elements.
Devu is only allowed to modify array B. In each step, he can change the value at some index in B to an arbitrary positive integer.
(Note that the new integer can be arbitrarily large, possibly much larger than what is allowed by the input constraints.)
Compute and return the minimum number of steps Devu needs to take.
Constraints
- A will have between 1 and 50 elements, inclusive.
- B will have between 1 and 50 elements, inclusive.
- Each element of A and B will be between 1 and 1012, inclusive.
{2, 3}
{6}
Returns: 0
The least common multiple of each array is 6. As the arrays already have the same LCM, no steps are needed.
{2, 6}
{4, 6}
Returns: 1
LCM(A) is 6 while LCM(B) is 12. You can change B[0] from 4 to 2 in a single step. This will clearly make the LCMs of both arrays equal (as now the arrays themselves are equal).
{4, 6, 10}
{7, 7, 60, 20}
Returns: 2
{5, 4, 6}
{7, 9, 13}
Returns: 3
{41,100,28,55,67,34,20,83,45,8,27,95,1,43,7,88,60,71,16,31,89,75,75,3,60,56,76,38,5}
{91,15,55,42,46,81,45,27,66,26,83,48,90,100,34,32,31,27}
Returns: 5
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DevuAndEqualizingLCM with a public method int minimumOperationsNeeded(vector<long long> A, vector<long long> B) · 114 test cases · 2 s / 256 MB per case