SWEGARR - Editorial



Author: Haresh Khanna
Tester: Vaibhav Daga
Editorialist: Haresh Khanna




Arrays, Sorting, Sweg


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.


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:

  1. 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.

  2. 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:



Author’s solution can be found here