Minimum operations to change given array with at most 1 duplicate into a permutation of 1 to N
Given an array arr[] having N integers in the range [1, N] with at most one repeated element, the task is to find the minimum number of increment or decrement operations required to make the given array a permutation of numbers from 1 to N.
Examples:
Input: arr[] = {1, 2, 5, 3, 2}
Output: 2
Explanation: The given array contains 2 twice and 4 is missing from the array. Therefore, a 2 can be changed into 4 using two increment operations which is the minimum possible.Input: arr[] = {1, 2, 5, 3, 4}
Output: 0
Explanation: The given array already represents the permutation of integers from 1 to 5.
Naive Approach: The given problem can be solved simply by finding the duplicate element and the missing element in the given array. This can be easily done by sorting the given array and checking for the duplicate and the missing element.
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Efficient Approach: The given problem can be solved using a simple observation that the sum of all elements of a permutation of N integers is always equal to N*(N+1)/ 2. Hence, the number of required operations can simply be calculated by the formula | sum of array elements – N*(N+1)/ 2)|.
Below is the implementation of the above approach:
CPP
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of // increment/decrement operations to change // the given array into a permutation int minCost( int arr[], int N) { // Stores the sum of array elements int sumOfArray = 0; // Loop to iterate through the array for ( int i = 0; i < N; i++) { sumOfArray += arr[i]; } // Finding sum of first // N natural numbers int sumOfN = N * (N + 1) / 2; // Find the absolute difference int diff = sumOfArray - sumOfN; diff = diff < 0 ? -1 * diff : diff; // Return Answer return diff; } // Driver code int main() { int arr[] = { 1, 2, 5, 3, 2 }; int n = sizeof (arr) / sizeof ( int ); cout << minCost(arr, n); return 0; } |
Java
// Java program of the above approach public class GFG { // Function to find the minimum number of // increment/decrement operations to change // the given array into a permutation static int minCost( int []arr, int N) { // Stores the sum of array elements int sumOfArray = 0 ; // Loop to iterate through the array for ( int i = 0 ; i < N; i++) { sumOfArray += arr[i]; } // Finding sum of first // N natural numbers int sumOfN = N * (N + 1 ) / 2 ; // Find the absolute difference int diff = sumOfArray - sumOfN; diff = diff < 0 ? - 1 * diff : diff; // Return Answer return diff; } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 5 , 3 , 2 }; int n = arr.length; System.out.println(minCost(arr, n)); } } // This code is contributed by AnkThon |
Python3
# python program of the above approach # Function to find the minimum number of # increment/decrement operations to change # the given array into a permutation def minCost(arr, N): # Stores the sum of array elements sumOfArray = 0 # Loop to iterate through the array for i in range ( 0 , N): sumOfArray + = arr[i] # Finding sum of first # N natural numbers sumOfN = N * (N + 1 ) / / 2 # Find the absolute difference diff = sumOfArray - sumOfN if diff < 0 : diff = - 1 * diff # Return Answer return diff # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 5 , 3 , 2 ] n = len (arr) print (minCost(arr, n)) # This code is contributed by rakeshsahni |
C#
// C# program of the above approach using System; class GFG { // Function to find the minimum number of // increment/decrement operations to change // the given array into a permutation static int minCost( int []arr, int N) { // Stores the sum of array elements int sumOfArray = 0; // Loop to iterate through the array for ( int i = 0; i < N; i++) { sumOfArray += arr[i]; } // Finding sum of first // N natural numbers int sumOfN = N * (N + 1) / 2; // Find the absolute difference int diff = sumOfArray - sumOfN; diff = diff < 0 ? -1 * diff : diff; // Return Answer return diff; } // Driver code public static void Main () { int []arr = { 1, 2, 5, 3, 2 }; int n = arr.Length; Console.Write(minCost(arr, n)); } } // This code is contributed by Samim Hossain Mondal |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum number of // increment/decrement operations to change // the given array into a permutation function minCost(arr, N) { // Stores the sum of array elements let sumOfArray = 0; // Loop to iterate through the array for (let i = 0; i < N; i++) { sumOfArray += arr[i]; } // Finding sum of first // N natural numbers let sumOfN = N * (N + 1) / 2; // Find the absolute difference let diff = sumOfArray - sumOfN; diff = diff < 0 ? -1 * diff : diff; // Return Answer return diff; } // Driver code let arr = [1, 2, 5, 3, 2]; let n = arr.length; document.write(minCost(arr, n)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)