Code question - Szymon Sysło

solution.js

// solution of a given problem - return new array based on two given arrays:
function makeSolution(firstList, secondList) {
  const memoizeNumbers = memo();
  const sortedArr = [...secondList].sort((a, b) => a - b);
  return firstList.reduce(
    (resultList, value) =>
      checkCanPush(value, sortedArr, memoizeNumbers)
        ? [...resultList, value]
        : resultList,
    []
  );
}

// if value is not memoized check is value quantity in given list is prime and memoize result; return converted or memoized result; 
function checkCanPush(value, inspectList, { has, get, set }) {
  if (has(value)) return get(value);
  const { valueQuantity, value: computedValue } = countValueQuantity(value, inspectList);
  const isPrime = checkIsPrime(valueQuantity);
  set(computedValue, isPrime);
  return isPrime ? false : true;
}

// how many times given value occur in array:
function countValueQuantity(value, arr) {
  let valueQuantity = 0;
  const firstFoundIndex = search(value, arr);
  if (firstFoundIndex === -1) return { valueQuantity, value };
  for (let i = firstFoundIndex; i < arr.length; i++) {
    if (value === arr[i]) valueQuantity++;
    if (arr[i] > value) break;
  }
  return { valueQuantity, value };
}

// Miller-Rabin primality test. Implementation of randomized version of the algorithm:
function checkIsPrime(number) {
  if (number < 2) return false;
  if (number === 2) return true;
  const accuracy = 100;
  let [d, r] = [number - 1, 0];
  while (!((d / 2) % 1)) {
    d /= 2;
    r++;
  }
  LoopLabel: for (let i = 0; i < accuracy; i++) {
    let a = Math.floor(Math.random() * (number - 4)) + 2;
    let x = 1;
    for (let z = 0; z < d; z++) {
      x = (x * a) % number;
    }
    if (x === 1 || x === number - 1) continue; 
    for (let j = 0; j < r - 1; j++) {
      x = (x * x) % number;
      if (x === 1) return false;
      if (x === number - 1) continue LoopLabel;
    }
    return false;
  }
  return true;
}

// modified binary search (return smallest index of given value in sorted list):
function search(value, list, isSorted = false) {
  if (list.length === 0) return -1;
  if (list.length === 1) return list[0] === value ? 0 : -1;
  const sortedList = isSorted ? list : [...list].sort((a, b) => a - b);
  let pivot = Math.floor(sortedList.length / 2);
  let currentFirst = 0;
  let currentLast = sortedList.length - 1;
  while (currentFirst < currentLast) {
    if (sortedList[pivot] < value) currentFirst = pivot + 1;
    else if (sortedList[pivot] > value) currentLast = pivot - 1;
    else {
      let firstFoundIndex = pivot;
      while (sortedList[firstFoundIndex] === value || firstFoundIndex > 0) {
        if (sortedList[firstFoundIndex - 1] !== value) return firstFoundIndex;
        firstFoundIndex--;
      }
      return firstFoundIndex;
    }
    pivot = Math.floor(currentFirst + (currentLast - currentFirst) / 2);
  }
  return -1;
}

// memoization service:
function memo() {
  const memoized = new Map();
  return {
    set: (key, value) => memoized.set(key, value),
    get: (key) => memoized.get(key),
    has: (value) => memoized.has(value),
  };
}

// sample arrays
const arrA = [2, 3, 9, 2, 5, 1, 3, 7, 10];
const arrB = [2, 1, 3, 4, 3, 10, 6, 6, 1, 7, 10, 10, 10];

//result
const arrC = makeSolution(arrA, arrB);

console.log(arrC);