1_algorithmic_task.ts

1_algorithmic_task.ts

// Write a function that receives two sequences:
// A and B of integers and returns one sequence C.
// Sequence C should contain all elements from sequence A (maintaining the order)
// except those, that are present in sequence B p times, where p is a prime number.

// Example:
// A=[2,3,9,2,5,1,3,7,10]
// B=[2,1,3,4,3,10,6,6,1,7,10,10,10]
// C=[2,9,2,5,7,10]

const A = [2, 3, 9, 2, 5, 1, 3, 7, 10];
const B = [2, 1, 3, 4, 3, 10, 6, 6, 1, 7, 10, 10, 10];

const isPrime = (p: number): boolean => {
    if (p < 2) {
        return false;
    }

    const upTo = Math.sqrt(p);

    for (let i = 2; i <= upTo; i++) {
        if (p % i === 0) {
            return false;
        }
    }

    return true;
};

const find = (A: Array<number>, B: Array<number>): Array<number> => {
    let countedB = {};

    B.forEach(num =>
        countedB[num] ? (countedB[num] = countedB[num] + 1) : (countedB[num] = 1)
    ); // O(n)

    const forbiddenNumbers = Object.entries(countedB) // O(n)
        .filter(([num, count]) => isPrime(count)) // O(n) * O(sqrt(n))
        .map(([num]) => Number(num)); // O(n)

    return A.filter(a => !forbiddenNumbers.includes(a)); // O(n^2) <-- TIME COMPLEXITY
};

find(A, B);