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 .
Making elements distinct in a sorted array by minimum increments.cpp
content_copyfile_download
//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);
}