HackerEarth Problem- Little Deepu and Array

general
, ,
1

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:

  1. keep an Original Array
  2. Create a vector of pairs of array elements and their index in the array
  3. Sort the vector elements [ ascending ]
  4. Do LowerBound() of C++ STL to get the position of element in the vector where elements are equal to give element.
  5. 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.
  6. Repeat step 4 & 5 for every x.
  7. Print the Original array.

I think my solution has complexity n^2.

Can someone Give me an Optimized solution

Thanks

My Code

2

Why are you doing so much,its a simple problem,just traverse the array whenever Hit(X) is called and if greater than X,update the value by decrementing it by 1.The time complexity turns out to be O(noofshots*sizeofarray)
Here’s my code:

include

using namespace std;

define ll long long

int main()
{
ll n;
cin>>n;
vector v(n);
for(int i=0;i<n;i++)
cin>>v[i];
ll shot;
cin>>shot;
while(shot–)
{
ll val;
cin>>val;
for(int i=0;i<n;i++)
{
if(v[i]>val)
v[i]–;
}
}
for(int i=0;i<n;i++)
{
cout<<v[i]<<" ";
}
return 0;
}

3

Why are you doing so much,its a simple problem,just traverse the array whenever Hit(X) is called and if greater than X,update the value by decrementing it by 1.The time complexity turns out to be O(no_of_shots*size_of_array)
Here’s my code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n;
cin>>n;
vector v(n);
for(int i=0;i<n;i++)
cin>>v[i];
ll shot;
cin>>shot;
while(shot–)
{
ll val;
cin>>val;
for(int i=0;i<n;i++)
{
if(v[i]>val)
v[i]–;
}
}
for(int i=0;i<n;i++)
{
cout<<v[i]<<" ";
}
return 0;
}