Ambiguous Permutations | CodeChef Solution

Hello coders, today we are going to solve Ambiguous Permutations CodeChef Solution whose Problem Code is PERMUT2.

Task

Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.
A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.

Input Specification

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.
The last test case is followed by a zero.

Output Specification

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output.

Sample Input

4
1 4 3 2
5
2 3 4 5 1
1
1
0

Sample Output

ambiguous
not ambiguous
ambiguous

Solution – Ambiguous Permutations | CodeChef Solution

C++

#include <iostream>
#include <stdlib.h>
using namespace std;

int main() {
	// your code goes here
	
	while(1)
	{
	    long int n, i, flag = 0;
	    cin >> n;
	    
	    if(!n)
	        break;
	    
	    long int arr[n];
	    for (i = 0; i < n; i++)
	        cin >> arr[i];
	        
	    for (i = 0; i < n; i++)
	        if (i + 1 != arr[arr[i] - 1])
	        {
	            flag = -1;
	            break;
	        }
	    
	    if (flag)
	        cout << "not ambiguous\n";
	    else
	        cout << "ambiguous\n";
	}
	
	return 0;
}

Python

#Solution Provided by CodingBroz
n = int(input())
while(n != 0):
    li = [int(i) for i in input().split()]
    li1 = list('0' * len(li))
    for i in range(len(li)):
        li1[li[i] - 1] = i + 1
    if(li == li1):
        print("ambiguous")
    else:
        print("not ambiguous")
    n = int(input()) 

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		while(true)
		{
		int N = sc.nextInt();
		int a[] = new int[N];
		int b[] = new int[N];
		int count = 0;
		for(int i = 0; i<N; i++)
		{
		    a[i] = sc.nextInt();
		    b[a[i]-1] = i+1;
		}
		if(N == 0)
		{
		    break;
		}
		for(int i = 0; i<N; i++)
		{
		  if(a[i] == b[i])
		  {
		      count++;
		  }
		}
		if(count == N)
		{
		    System.out.println("ambiguous");
		}
		else
		{
		    System.out.println("not ambiguous");
		}
		}
	}
}

Disclaimer: The above Problem (Ambiguous Permutations) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.