Arrays: Convert an array into permutation of numbers from 1 to N.

Problem Statement:

You are given an array of length n.

You need to count the minimum number of operations to make the array into permutation of first n natural numbers.

You can do increment or decrement in each operation.

Example:

Input: arr[] = {4, 1, 3, 6, 5} 
Output: 4 

Need to decrement 6, 4 times to make the array permutation.

Solution Explanation:

Solution is very simple.

Sort the array and for each element find the different between arr[i] and i based on indexing.

Find the sum of all such difference and add them that will be the minimum steps required.

Time Complexity: O(n*log(n))
Space Complexity: O(1)

Code Solution

#include<iostream>
#include<algorithm>
using namespace std;

int solution(int arr[], int n)
{
	// Sort the array
	sort(arr, arr + n);

	int result = 0;

	for (int i = 0; i < n; i++) 
	{
		result += abs(arr[i] - (i + 1));
	}

	return result;
}

int main()
{
	int arr[] = { 4, 1, 4, 2 };

	int n = sizeof(arr) / sizeof(arr[0]);
	cout << solution(arr, n);

	return 0;
}

Output

1