Given a sorted integer array. We need to make array elements distinct by increasing values and keeping the array sum minimum possible. We need to print the minimum possible sum as output.
Note :- After increasing the values of the array , the sorted order should be maintained.
 
Example 1:
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
Example 2:
Input : arr[ ] = {20, 20} 
Output :  41
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function minSum() that takes an array (arr), sizeOfArray (n), and return the minimum possible sum. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3





def minSum (arr, n) : 

    #Complete the function





Solutions:
def minSum(arr, n):
	for i in range(1, n):
		if arr[i] <= arr[i - 1]:
			arr[i] = arr[i - 1] + 1
	return sum(arr)


def minSum(arr, n):
	n = len(arr)
	for i in range(1, n):
		if arr[i - 1] >= arr[i]:
			arr[i] = arr[i - 1] + 1
	c = 0
	for i in range(0, n):
		c = c + arr[i]
	return c


def minSum(arr, n):
	min_sum = arr[0]
	prev = arr[0]
	for i in range(1, n):
		if arr[i] <= prev:
			prev += 1
			min_sum += prev
		else:
			min_sum += arr[i]
			prev = arr[i]
	return min_sum


def minSum(arr, n):
	ans = arr[0]
	c = arr[0]
	for i in arr[1:]:
		if i <= c:
			ans += c + 1
			c = c + 1
		else:
			c = i
			ans += i
	return ans


def minSum(arr, n):
	sum = arr[0]
	prev = arr[0]
	for i in range(1, n):
		if arr[i] <= prev:
			prev = prev + 1
			sum = sum + prev
		else:
			sum = sum + arr[i]
			prev = arr[i]
	return sum
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = minSum(arr, n)
	print(res)


def minSum(arr, n):
	sm = arr[0]
	j = arr[0]
	for i in range(1, n):
		if arr[i] <= j:
			j = j + 1
			sm = sm + j
		else:
			sm = sm + arr[i]
			j = arr[i]
	return sm