Permutations

Permutations

Help

Solution 01:

	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 1000006;
	int n,p[maxn], vist[maxn], ans;
	void solve()
	{
	ans = 0;
	for(int i = 1; i <= n; i++)
	{
	if(!vist[i]){
	int cnt = 0;
	while(!vist[i])
	{
	vist[i] = 1;
	i = p[i];
	cnt++;
	}
	if(cnt & (cnt - 1)){
	cout << "-1\n";
	return;
	}
	ans = max(ans, cnt);
	}
	}
	cout << log2(ans)<<endl;
	}
	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
	cin >> p[i];
	vist[i] = 0;
	}
	solve();
	}
	return 0;
	}

view raw HackerEarth.cpp hosted with ❤ by GitHub

Solution 02:

	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 1000006;
	int n,p[maxn], vist[maxn], ans, cnt;
	void dfs(int x)
	{
	vist[x] = 1;
	cnt++;
	if(!vist[p[x]])
	dfs(p[x]);
	}
	int calc(int &a)
	{
	int res = 0;
	while(a%2 == 0){
	a /= 2;
	res++;
	}
	return res;
	}
	void solve()
	{
	int f = 0;
	int val;
	ans = 0;
	for(int i = 1; i <= n; i++)
	{
	cnt = 0;
	if(!vist[i]){
	dfs(i);
	val = calc(cnt);
	if(cnt != 1) f = 1;
	else ans = max(ans, val);
	}
	}
	if(f) cout << -1<<endl;
	else cout << ans << endl;
	}
	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
	cin >> p[i];
	vist[i] = 0;
	}
	solve();
	}
	return 0;
	}

view raw HackerEarth2.cpp hosted with ❤ by GitHub

Share: