PROBLEM LINK:
Author: Haresh Khanna
Tester: Vaibhav Daga
Editorialist: Haresh Khanna
Difficulty:
Easy
Prerequisites:
Arrays, Sorting, Sweg
PROBLEM:
Given an array A of size N and each element of the array lies in the range [L,R] (inclusive). You have to choose exactly one integer from the array and replace it with another integer that also lies in the range [L,R] inclusive. You necessarily have to change a number and you can’t change a number with itself. After the replacement sort the array and output the minimum integer that could occur at each position after the replacement and sorting.
EXPLANATION:
It is clear from the problem statement that we have to choose a number then change it to some number in in range of [L,R] and then sort the array and output. Now in the first place there are ‘n’ numbers that can be replaced and (R-L-1) possibilities for each. Now we will get the minimum at each position when we replace the maximum number of the array Amax by the minimum number in [L,R] i.e. L. This can be achieved by first sorting. Let the sorted array be called B. Now print “L” followed by the n-1 numbers from B[0] to B[n-2]. This effectively means replacing B[n-1] (max element of A) by L and printing the sorted array A after the replacement, which is the required answer.
But there are fails in this approach considering the fact that a number needs to be replaced necessarily and it can not be replaced by itself. So the two fails are:
-
All the numbers of the given array are L and L!=R: In this case after sorting, in array B, B[n-1] will be L and if we apply the previously discussed approach we will end up not replacing anything. So to cover this case and consider we have to replace necessarily we replace B[n-1] with L+1 and output the array B.
-
L is equal to R: In this case, all the number of the array are equal to L and any number can not be changed as there is no number in [L,R] except L itself. So “-1” needs to be printed.
Time Complexity:
O(n*log(n))
AUTHOR’S SOLUTION:
Author’s solution can be found here