In this HackerEarth Sorted Arrays problem solution, Alice has recently found an array containing N integers. As we all know Alice loves sorted arrays so, he wants to sort the array. To sort an array Alice can add 1 to any integer in the array in 1 move.

Alice wants to find a minimum number of moves needed to sort this array. Remember that after sorting the array, all elements in it should be distinct.


HackerEarth Sorted Arrays problem solution


HackerEarth Sorted Arrays problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define MM 1000000009
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "\n"
#define inf 100000000000000
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[1000001];
int main()
  {
    ios_base::sync_with_stdio(0);
    int n;
    LL ans = 0;
    cin >> n;
    a[0] = 0;
    for(int i = 1; i <= n ; i++)
      {
        cin >> a[i];
        if(a[i] <= a[i - 1])
          {
            ans = ans + a[i - 1] - a[i] + 1;
            a[i]  = a[i - 1] + 1;
          }
      }
    cout << ans;
  }