AbsDistinct

Compute number of distinct absolute values of sorted array elements
ℹ️ © Codility, 2009-2018

Problem

A non-empty array A consisting of n numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that: A[0] = -5, A[1] = -3, A[2] = -1, A[3] = 0, A[4] = 3, A[5] = 6.
The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function that, given a non-empty array A consisting of n numbers, returns absolute distinct count of array A.

For example, given array A such that: A[0] = -5, A[1] = -3, A[2] = -1, A[3] = 0, A[4] = 3, A[5] = 6, the function should return 5, as explained above.

Assume that:
• n is an integer within the range [1 … 100,000];
• each element of array A is an integer within the range [-2,147,483,648 … 2,147,483,647];
• array A is sorted in non-decreasing order.

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

Elements of input arrays can be modified.

Solution

C#

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

Java

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

JavaScript

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

PHP

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