Problem:
An Array of positive elements. Deepu Wants to reduce the elements of the array.
He calls a function Hit(X) which reduces the all the elements in the array which are greater than X by 1.
he will call this array many times . Print the array after many calls to Hit(X).
Input:
n----- no of elements in array 10^5.
n elements ----- 1<=element<=10^9.
x----- no of calls to Hit(X)
x elements----- 1<=element<=10^9.
output:
Print The array after call to Hit(X) x times.
Time limit–5 secs.
My solution gave Time Limit Exceeded.
My approach:
- keep an Original Array
- Create a vector of pairs of array elements and their index in the array
- Sort the vector elements [ ascending ]
- Do LowerBound() of C++ STL to get the position of element in the vector where elements are equal to give element.
- From this element decrease the elements which are greater than x by 1 till end in the original array from the index in the pair.
- Repeat step 4 & 5 for every x.
- Print the Original array.
I think my solution has complexity n^2.
Can someone Give me an Optimized solution
Thanks