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.
//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);
}