Home » Interview Questions » Hashing Interview Questions » Change the Array into Permutation of Numbers From 1 to N

Change the Array into Permutation of Numbers From 1 to N


()

In this problem, we have given an array A of n elements. We need to change the array into a permutation of numbers from 1 to n using minimum replacements in the array.

Example

Input:

2 2 3 3

Output:

2 1 3 4

Input :

3 2 1 7 8 3

Output:

3 2 1 4 5 6

Main idea for Change the Array into Permutation of Numbers From 1 to N

First, we will store all the missing elements in a set. After that, we will maintain a hash table which will store whether we have printed or not and if we have already printed an element and it comes again in the array then it means we have to print a missing element instead of this element so we will print an element from our set and then erase that element from our set.

Algorithm

  1. Make a set of all the numbers from 1 to n;
  2. Iterate the array and remove all the array elements from the set.
  3. Declare a hash table and initialize all its values with false.
  4. Iterate the array for I in range 1 to n-1
    • If we have not printed arr[i] then print arr[i] and mark it as true in the hash table.
    • Else if we have already printed arr[i], then print the first element from the set and remove that element from the set.
  5. Return.

Implementation for Change the Array into Permutation of Numbers From 1 to N

C++ program

#include <bits/stdc++.h>
using namespace std;
void makePermutation(vector<int> a, 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(a[i]))
        {
            s.erase(a[i]);
        }
    }
    vector<bool> m(n + 1, false);
    for (int i = 0; i < n; i++)
    {
        if ((a[i] <= n) and (a[i] > 0) and (m[a[i]] == 0))
        {
            m[a[i]] = true;
            cout << a[i] << " ";
        }
        else
        {
            int missing_number = *s.begin();
            m[missing_number] = true;
            s.erase(s.begin());
            cout << missing_number << " ";
        }
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    makePermutation(a, n);
    return 0;
}
2 2 3 3
2 1 3 4

JAVA program

import java.util.*;
public class Main
{
    public static void makePermutation(int[] a, int n)
    {
        Set<Integer> s = new HashSet<Integer>(); 
        for (int i = 1; i <= n; i++)
        {
            s.add(i);
        }
        for (int i = 0; i < n; i++)
        {
            if (s.contains(a[i]))
            {
                s.remove(a[i]);
            }
        }
        boolean[] m = new boolean[n+1];
        for (int i = 0; i < n; i++)
        {
            if ((a[i] <= n) && (a[i] > 0) && (m[a[i]] == false))
            {
                m[a[i]] = true;
                System.out.print(a[i]+" ");
            }
            else
            {
                int missing_number = (s.iterator()).next();
                m[missing_number] = true;
                s.remove(missing_number);
                System.out.print(missing_number+" ");
            }
        }
        return;
    }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      for(int i=0;i<n;i++){
          a[i] = sc.nextInt();
      }
      makePermutation(a, n);
  }
}

5
1 5 3 7 6
1 5 3 2 4

Complexity Analysis for Change the Array into Permutation of Numbers From 1 to N

Time complexity

O(NlogN) because to prepare the set of missing elements, we iterate from 1 to n, and each insertion takes logn time so, the total time complexity is O(N*logN).

READ  Next Greater Frequency Element

Space complexity

O(N) because here we have taken and extra set and a hash table both of size N, so our space complexity is O(N)

References

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions