PermCheck

Check whether array A is a permutation
ℹ️ © Codility, 2009-2018

Problem

A non-empty array A consisting of n integers is given.
A “permutation” is a sequence containing each element from 1 to n once, and only once.

For example, array A such that: A[0] = 4, A[1] = 1, A[2] = 3, A[3] = 2, is a permutation, but array A such that: A[0] = 4, A[1] = 1, A[2] = 3, is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that: A[0] = 4, A[1] = 1, A[2] = 3, A[3] = 2, the function should return 1.
Given array A such that: A[0] = 4, A[1] = 1, A[2] = 3, the function should return 0.

Assume that:
• n is an integer within the range [1 … 100,000];
• each element of array A is an integer within the range [1 … 1,000,000,000].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

Solution

C#

using System;
class Solution {
  public int solution(int[] A) {
    Array.Sort(A);
    int n = A.Length;
    for (int i = 1; i <= n; i++) {
      if (A[i - 1] != i) {
        return 0;
      }
    }
    return 1;
  }
}

Java

import java.util.Arrays;
class Solution {
  public int solution(int[] A) {
    Arrays.sort(A);
    int n = A.length;
    for (int i = 1; i <= n; i++) {
      if (A[i - 1] != i) {
        return 0;
      }
    }
    return 1;
  }
}

JavaScript

function solution(A) {
  A.sort((a, b) => a - b);
  let n = A.length;
  for (let i = 1; i <= n; i++) {
    if (A[i - 1] != i) {
      return 0;
    }
  }
  return 1;
}

PHP

function solution($A) {
  sort($A);
  $n = count($A);
  for ($i = 1; $i <= $n; $i++) {
    if ($A[$i - 1] != $i) {
      return 0;
    }
  }
  return 1;
}