Change the Array into a Permutation of Numbers from 1 to n

Approach

To change the array into a permutation of numbers from 1 to n, Keep in mind that separate numbers within the range [1, n] don't need to be changed (the number with only one occurrence). Thus, we choose a greedy strategy. If a number between 1 and n that we have never encountered before appears, we leave it alone. We will add the missing elements in the range [1, n] after removing the duplicate elements. Change any numbers that are not in the range as well.

Also read, Permutation of string

ALGORITHM

1. Create a set containing every number from 1 to n.
    
2. Iterate the array and remove every array element.
    
3. Declare a hash table and set all of its values to false at the beginning.
    
4. Repeat the array iterations for i from 1 to n-1.
    
5. If we haven't already, print arr[i] and mark it as true in the hash table.
    
6. Otherwise, print the first member from the set and remove it from the set if we have already printed arr[i].
    
7. Return

Step-wise Explanation of Algorithm:

Let us take the array as:

arr[] = { 8 ,1, 2, 3 };

1. Here n = 4.
    
2. So we need to change the array into a permutation of numbers from 1 to 4.
    
3. Now we will create a set that will store every number from 1 to n. Therefore set will contain {1, 2, 3, 4}.
    
4. Now we will iterate from 1 to n in a for loop and remove every array element from the set. After removal, the set will be = {4} as 1, 2, 3 will be removed.
    
5. Now we will create a hash table and initialize every value with false.
    
6. Now we will iterate in a for loop from 1 to n-1 (4 - 1 = 3).
    
7. Now in this loop, we will print arr[i] if we haven’t printed that number before and mark it as true in the hash table.
    
8. If the number is already printed then we will print the first element of the set and remove it from the set.
    
9. So the first number is 8, which is less than n, so it will not be printed and thus the first element of the set which is 4, will be printed instead of 8.
    
10. Therefore, in the end, {4, 1, 2, 3} will be printed.

C++ CODE

Implementation in C++ to Change the Array into a Permutation of Numbers from 1 to n.

#include <bits/stdc++.h>
using namespace std;

void makePermutation(vector<int> arr, int n)
{
	set<int> s;
	for (int i = 1; i <= n; i++)
	{
		s.insert(i);
	}
	for (int i = 0; i < n; i++)
	{
		if (s.count(arr[i]))
		{
			s.erase(arr[i]);
		}
	}
	
	vector<bool> temp(n + 1, false);
	
	for (int i = 0; i < n; i++)
	{
		if ((arr[i] <= n) and (arr[i] > 0) and (temp[arr[i]] == 0))
		{
			temp[arr[i]] = true;
			cout << arr[i] << " ";
		}
		else
		{
			int missingNumber = *s.begin();
			temp[missingNumber] = true;
			s.erase(s.begin());
			cout << missingNumber << " ";
		}
	}
}

int main()
{
	int n;
	cin >> n;
	vector<int> arr(n);
	
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	
	makePermutation(arr, n);
	return 0;
}

INPUT

4
2, 5, 2, 3

OUTPUT

2 1 3 4

JAVA CODE

Implementation in Java to Change the Array into a Permutation of Numbers from 1 to n.

import java.util.*;

class work
{
	static void makePermutation(int []arr, int n)
	{
		HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
		for (int i = 0; i < n; i++)
		{
			if(count.containsKey(arr[i]))
			{
				count.put(arr[i], count.get(arr[i]) + 1);
			}
			else
			{
				count.put(arr[i], 1);
			}
		}

		int nextMissing = 1;
		for (int i = 0; i < n; i++)
		{
			if (count.containsKey(arr[i]) && count.get(arr[i]) != 1 || arr[i] > n || arr[i] < 1)
			{
				count.put(arr[i], count.get(arr[i]) - 1);
				while (count.containsKey(nextMissing))
					nextMissing++;

				arr[i] = nextMissing;
				count. put(nextMissing, 1);
			}
		}
	}

	// Driver Code
	public static void main(String[] args)
	{
		int arr[] = {8, 1, 2, 4};
		int n = arr.length;
		makePermutation(arr, n);
		for (int i = 0; i < n; i++)
			System.out.print(arr[i] + " ");
	}
}

OUTPUT

3, 1, 2, 4

PYTHON CODE

Implementation in Python to Change the Array into a Permutation of Numbers from 1 to n.

def makePermutation (arr, n):
	count = dict()
	for i in range(n):
		if count.get(arr[i]):
			count[arr[i]] += 1
		else:
			count[arr[i]] = 1;
	
	nextMissing = 1
	for i in range(n):
		if count[arr[i]] != 1 or arr[i] > n or arr[i] < 1:
			count[arr[i]] -= 1

			while count.get(nextMissing):
				nextMissing+=1

			arr[i] = nextMissing
			count[nextMissing] = 1

# Driver Code
arr = [1, 3, 2]
n = len(arr)
makePermutation(arr, n)

for i in range(n):
	print(arr[i], end = " ")

OUTPUT

1, 3, 2

Time Complexity

Because we iterate from 1 to n to prepare the set of missing pieces, and each insertion requires logn time, the total time complexity is O(N*logN). [where n represents the total number of elements in the array].

Space Complexity

Due to the fact that we have taken an additional set and a hash table of size N in this case, our space complexity is O(N). [where n represents the total number of elements in the array].

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What can be done with a hash table?

Key/value pairs are kept in a data structure called a hash table. To determine the index into an array where an element will be inserted or searched, it uses a hash function.

Can Hashtable have duplicate keys?

Hashtables can only contain unique keys by design. Therefore duplicate keys cannot be added to them.

What is the load factor of a hash table?

The definition of a load factor is (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.

What is the time complexity of the above approach to solve the question?

The time complexity of the above approach where the hash map has been used is O(nlogn).

What will be the space complexity of the above approach to solve the question?

The space complexity of the above approach where the hash map has been used is O(n).

Conclusion

In this article, we have extensively discussed, Change the Array into a Permutation of Numbers from 1 to n. We hope this blog has helped you understand this sum.

If you want to learn more, check out our articles on Distribute maximum number of chocolates amongst X students, Winner of Tic-tac-toe, Reduce Array Size to The half, Minimum number of subsets with distinct elements, and Remove minimum number of elements such that no common element exist in both array.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k
• Search In Rotated Sorted Array

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!