Minimize sum of numbers required to convert an array into a permutation of first N natural numbers - Coding

Given an array A[] of size N, the task is to find the minimum sum of numbers required to be added to array elements to convert the array into a permutation of 1 to N. If the array can not be converted to desired permutation, print -1.

Examples:

Input: A[] = {1, 1, 1, 1, 1}
Output: 10
Explanation: Increment A[1] by 1, A[2] by 2, A[3] by 3, A[4] by 4, thus A[] becomes {1, 2, 3, 4, 5}.
Minimum additions required = 1 + 2 + 3 + 4 = 10

Input: A[] = {2, 2, 3}
Output: -1

Approach: The idea is to use sorting. Follow these steps to solve this problem:

Initialize a variable ans to store the required result.
Sort the given array A[] in increasing order.
Traverse the array, A[] using the variable i
- If the value of A[i] > i+1, update ans to -1 and break out of the loop.
- Else increment ans by the difference of i+1 and A[i].
Print the value of ans as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum additions required 
// to convert the array into a permutation of 1 to N
int minimumAdditions(int a[], int n)
{
    // Sort the array in increasing order
    sort(a, a + n);
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If a[i] > i + 1, then return -1
        if ((i + 1) - a[i] < 0) {
            return -1;
        }
        if ((i + 1) - a[i] > 0) {
 
            // Update answer
            ans += (i + 1 - a[i]);
        }
    }
 
    // Return the required result
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int A[] = { 1, 1, 1, 1, 1 };
    int n = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << minimumAdditions(A, n);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.Arrays;
 
public class GFG {
 
    // Function to find the minimum additions required 
    // to convert the array into a permutation of 1 to N
    static int minimumAdditions(int a[], int n)
    {
        // Sort the array in increasing order
        Arrays.sort(a);
        int ans = 0;
 
        // Traverse the array
        for (int i = 0; i < n; i++) {
 
            // If a[i] > i + 1, then return -1
            if ((i + 1) - a[i] < 0) {
                return -1;
            }
            if ((i + 1) - a[i] > 0) {
 
                // Update answer
                ans += (i + 1 - a[i]);
            }
        }
 
        // Return the required result
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    { 
       
      // Given Input
        int A[] = { 1, 1, 1, 1, 1 };
        int n = A.length;
 
        // Function Call
        System.out.println(minimumAdditions(A, n));
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Function to find the minimum additions
# required to convert the array into a 
# permutation of 1 to N
def minimumAdditions(a, n):
     
    # Sort the array in increasing order
    a = sorted(a)
    ans = 0
 
    # Traverse the array
    for i in range(n):
 
        # If a[i] > i + 1, then return -1
        if ((i + 1) - a[i] < 0):
            return -1
 
        if ((i + 1) - a[i] > 0):
 
            # Update answer
            ans += (i + 1 - a[i])
 
    # Return the required result
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    A = [ 1, 1, 1, 1, 1 ]
    n = len(A)
 
    # Function Call
    print(minimumAdditions(A, n))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the minimum additions
// required to convert the array into a
// permutation of 1 to N
static int minimumAdditions(int []a, int n)
{
     
    // Sort the array in increasing order
    Array.Sort(a);
    int ans = 0;
 
    // Traverse the array
    for(int i = 0; i < n; i++) 
    {
         
        // If a[i] > i + 1, then return -1
        if ((i + 1) - a[i] < 0) 
        {
            return -1;
        }
         
        if ((i + 1) - a[i] > 0) 
        {
             
            // Update answer
            ans += (i + 1 - a[i]);
        }
    }
 
    // Return the required result
    return ans;
}
 
// Driver code
static void Main()
{ 
     
    // Given Input
    int[] A = { 1, 1, 1, 1, 1 };
    int n = A.Length;
     
    // Function Call
    Console.Write(minimumAdditions(A, n));
}
}
 
// This code is contributed by SoumikMondal

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the minimum additions required 
    // to convert the array into a permutation of 1 to N
function minimumAdditions(a, n)
{
 
    // Sort the array in increasing order
        a.sort(function(a, b){return a-b;});
        let ans = 0;
  
        // Traverse the array
        for (let i = 0; i < n; i++) {
  
            // If a[i] > i + 1, then return -1
            if ((i + 1) - a[i] < 0) {
                return -1;
            }
            if ((i + 1) - a[i] > 0) {
  
                // Update answer
                ans += (i + 1 - a[i]);
            }
        }
  
        // Return the required result
        return ans;
}
 
// Driver code
// Given Input
let A = [ 1, 1, 1, 1, 1 ];
let n = A.length;
 
// Function Call
document.write(minimumAdditions(A, n));
 
// This code is contributed by unknown2108
</script>

Output:

Time Complexity: O(N* log(N))
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array
Split an array into subarrays with maximum Bitwise XOR of their respective Bitwise OR values
Minimize sum of points assigned to distinct elements present in an array
Split array into K subarrays such that sum of maximum of all subarrays is maximized
Minimize maximum difference between any pair of array elements by exactly one removal

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	9