ronith
10/10/2018 - 8:46 AM

## Making elements distinct in a sorted array by minimum increments

Given a sorted integer array. We need to make array elements distinct by increasing values and keeping array sum minimum possible. We need to print the minimum possible sum as output.

Examples:

Input : arr[] = { 2, 2, 3, 5, 6 } ; Output : 20 Explanation : We make the array as {2, 3, 4, 5, 6}. Sum becomes 2 + 3 + 4 + 5 + 6 = 20

Input : arr[] = { 20, 20 } ; Output : 41 Explanation : We make {20, 21}

Input : arr[] = { 3, 4, 6, 8 }; Output : 21 Explanation : All elements are unique so result is sum of each elements.

1. Traverse each element of array .
2. if arr[i] <= prev then pdate prev by adding 1 and update sum by adding prev. Else update prev by cur element and update sum by adding cur element(arr[i]).
3. After traversing of each element return sum .
//https://www.geeksforgeeks.org/making-elements-distinct-sorted-array-minimum-increments/
#include <iostream>
using namespace std;

int func (int a[], int n) {
int prev= a[0], sum= a[0];
for (int i=1;i<n; i++) {
if (a[i]<=prev) {
prev+= 1;
sum+= prev;
}
else {
prev= a[i];
sum+= a[i];
}
}
return sum;
}

int main() {
int n;
cin>>n;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i];
cout<<func(a,n);
}