Given an array arr of positive integers of size N, the task is to find the minimum cost to make this array a permutation of first N natural numbers, where the cost of incrementing or decrementing an element by 1 is 1.
Examples:
Input: arr[] = {1, 1, 7, 4}
Output: 5
Explanation:
Perform increment operation on 1 one time
Perform decrement operation on 7 four times
Resultant array = {1, 2, 3, 4}
Input: arr[] = {1, 2, 3, 4, 5}
Output: 0
Explanation:
The array is already a permutation.
Approach:
- Sort the array element in increasing order
- Traverse the sorted array:
- Check if the element at ith index (0 ? i < N) is equals to i + 1.
- If not, then make it equal and increment the difference between the two as the cost of this operation.
- When the traversal is complete, print the total cost of the operations performed.
Below is the implementation of the above approach:
C++
// C++ program to calculate minimum cost// to make an Array a permutation// of first N natural numbers#include <bits/stdc++.h>using namespace std;// Function to calculate minimum cost// for making permutation of size Nint make_permutation(int arr[], int n){ // sorting the array in ascending order sort(arr, arr + n); // To store the required answer int ans = 0; // Traverse the whole array for (int i = 0; i < n; i++) ans += abs(i + 1 - arr[i]); // Return the required answer return ans;}// Driver codeint main(){ int arr[] = { 5, 3, 8, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << make_permutation(arr, n);} |
Java
// Java program to calculate minimum cost// to make an Array a permutation// of first N natural numbersimport java.util.*;class GFG{ // Function to calculate minimum cost// for making permutation of size Nstatic int make_permutation(int arr[], int n){ // sorting the array in ascending order Arrays.sort(arr); // To store the required answer int ans = 0; // Traverse the whole array for (int i = 0; i < n; i++) ans += Math.abs(i + 1 - arr[i]); // Return the required answer return ans;} // Driver codepublic static void main(String[] args){ int arr[] = { 5, 3, 8, 1, 1 }; int n = arr.length; // Function call System.out.print(make_permutation(arr, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to calculate minimum cost # to make an Array a permutation # of first N natural numbers # Function to calculate minimum cost # for making permutation of size N def make_permutation(arr, n) : # sorting the array in ascending order arr.sort(); # To store the required answer ans = 0; # Traverse the whole array for i in range(n) : ans += abs(i + 1 - arr[i]); # Return the required answer return ans; # Driver code if __name__ == "__main__" : arr = [ 5, 3, 8, 1, 1 ]; n = len(arr); # Function call print(make_permutation(arr, n)); # This code is contributed by Yash_R |
C#
// C# program to calculate minimum cost// to make an Array a permutation// of first N natural numbersusing System;class GFG{ // Function to calculate minimum cost // for making permutation of size N static int make_permutation(int []arr, int n) { // sorting the array in ascending order Array.Sort(arr); // To store the required answer int ans = 0; // Traverse the whole array for (int i = 0; i < n; i++) ans += Math.Abs(i + 1 - arr[i]); // Return the required answer return ans; } // Driver code public static void Main(string[] args) { int []arr = { 5, 3, 8, 1, 1 }; int n = arr.Length; // Function call Console.WriteLine(make_permutation(arr, n)); }}// This code is contributed by Yash_R |
Javascript
<script>// Java Script program to calculate minimum cost// to make an Array a permutation// of first N natural numbers// Function to calculate minimum cost// for making permutation of size Nfunction make_permutation(arr,n){ // sorting the array in ascending order arr.sort(); // To store the required answer let ans = 0; // Traverse the whole array for (let i = 0; i < n; i++) ans += Math.abs(i + 1 - arr[i]); // Return the required answer return ans;}// Driver code let arr = [ 5, 3, 8, 1, 1 ]; let n = arr.length; // Function call document.write(make_permutation(arr, n));// contributed by sravan kumar</script> |
Output:
5
Time Complexity: O(n*log(n))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
