PermMissingElement

Find the missing element in a given permutation
ℹ️ © Codility, 2009-2018

Problem

An array A consisting of n different integers is given. The array contains integers in the range [1 … (n + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.

Write a function that, given an array A, returns the value of the missing element.

For example, given array A such that: A[0] = 2, A[1] = 3, A[2] = 1, A[3] = 5, the function should return 4, as it is the missing element.

Assume that:
• n is an integer within the range [0 … 100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1 … (n + 1)].

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

Solution

C#

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

Java

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

JavaScript

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

PHP

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