Editorial for Changing Volume, Dominated Subarray, Fadi and LCM

Problem Discussed Today
  1. Changing Volume ( 1255A )
  2. Dominated Subarray ( 1257C )
  3. Fadi and LCM ( 1285C )

Interview Problem ( From LeetCode )
  1. Two City Scheduling
Editorial 
1. Changing Volume ( 1255A )
In this problem, a and b are given and we need to find the minimum number of operation required to make a = b by either incrementing or decrementing by 1,2,5.
So the idea here is to get the difference between a and b and then find minimum steps required to form this number from the given 1,2,5.

Eg, if a=5 b=12 then, the difference is of 7, and 7 can be formed in two steps by using 5 and 2. 

Solution Link: Solution


In this problem, we need to find the shortest dominated array. Now let us understand this through this example, the given array is 1,2,3,4,5,1. Now we can find a dominated subarray whenever we get the same element twice and the distance between there position would be the length of the subarray. And a minimum of those distance is our answer.

Now to store the last position of the seen element we will maintain an array of size n+1. And the distance between the last seen and current number would be i- arr[x], where x is the ith input element. Initially, arr[x] have -∞. And the answer would be minimum (i-arr[x]) over the input array.


Solution Link: Solution


This question asks us to find the minimum possible value of max(a,b) such that LCM(a,b)=X. And X can take value up to 10^12. So in this problem, we cannot even use the linear algorithm we need to look for Sublinear Algorithm.

Here can guarantee that the number a,b will be the divisor of X and we can find all the divisors increasing order in O(sqrt(n)) time complexity. Now considering that we have got this. We can again guarantee here that to get LCM(a,b) = X we need to take a from left half and b from the right half.

For example, X = 12. All divisors are 1, 2, 3, 4, 6, 12. And the possible option to check will be the following.


Here, we cannot take (a,b) from right side as either they will be greater than X. Similarly we can not take both a,b from left side as they will always be less than X. So we just need to check for index (n/2,n/2+1), (n/2-1,n/2+2) and so own and for other pairs of indices, they will be less or more but not equal so we don't need to check for them. Once we find the first such pair then we have got the solution and no need to iterate so break. That's done.

Solution Link: Solution

If there is an error or want to discuss your approach, then please feel free to drop in the comment section.

Thank You

Comments