Hashing: Given an array, check if the array is a permutation of numbers from 1 to N.

Problem Statement:

You are given an array, you need to find if the array is a permutation of 1 to N numbers.

Example:

Input: [1, 2, 4, 4, 3]
Output: No

Input: [1, 2, 4, 3, 5]
Output: Yes

Solution:

We will use Hash Table to solve the problem.

Traverse through the array and store the frequency of each number.

Now traverse the HashTable and check if all the numbers from 1 to N have the frequency 1 or not and display the result.

Time Complexity: O(N)
Space Complexity: O(N)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;

string solution(vector<int> arr)
{
	set<int> s;
	int i = 0;

	for (i = 0; i <= arr.size()-1; i++)
	{
		s.insert(arr[i]);
	}
    
    i = 1;
    for (auto x : s){
        cout << x <<" "<< i<< endl;
        if(x != i)
            return "No";
        i++;
    }
            return "Yes";
}

int main()
{
    vector<int> arr = {1, 2, 4, 3, 5};
    
    cout << solution(arr) << endl;
	return 0;
}

Output

Yes