leeDistance function

int leeDistance(
  1. List<int> source,
  2. List<int> target,
  3. int q
)

Finds the Lee distance between two lists.

Parameters

  • source and target are two list of items.
  • q is the alphabet size. It must be greater than 1.

Details

In coding theory, Lee distance is a distance between two equal-length list of items over a q-ary alphabet {0, 1, ..., q - 1} of size q >= 2.

  • The lee distance between two item x and y is min(|x - y|, q - |x - y|)
  • The lee distance between two strings is the summation of all lee distances from index 0 to n.

If two list are not equal, a RangeError is thrown.

Complexity: Time O(n) | Space O(1)

Implementation

int leeDistance(List<int> source, List<int> target, int q) {
  int n = source.length;
  int m = target.length;
  if (n != m) {
    throw RangeError('source and target must have equal length');
  }

  int i, c, d = 0;
  for (i = 0; i < n; i++) {
    c = source[i] - target[i];
    if (c < 0) c = -c;
    d += min(c, q - c);
  }

  return d;
}