Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- object CompositeOccurrences extends App {
- /**
- * Brute force primality test, takes sqrt(x) time with a silent assumption than divisibility checking takes O(1).
- */
- private def isPrime(x: Int): Boolean = {
- assert(x >= 0)
- if (x < 2) return false
- else if (x == 2) return true
- val i = 2
- while (i*i <= x) {
- if (x % i == 0) return false
- }
- true
- }
- /**
- * Returns all elements from sequence A (maintaining the order) except those, that are present in sequence B p times,
- * where p is a prime number.
- */
- def compositeOccurrences(A: Seq[Int], B: Seq[Int]): Seq[Int] = {
- // creating map of B elements takes O(n log n) time (groupBy), where is n is B size.
- val occurrences = B.groupBy(x => x).mapValues(_.length)
- // For every element in A (of size O(m)) we do primality test on number of occurrences in B. They are potentially unlimited,
- // however let's make assumption that size of B is also O(m). If s_1, ..., s_m represents numbers of occurrences of elements of A in B,
- // then filtering A takes approximately sqrt(s1) + ... + sqrt(s_m) <= m. So the overall complexity would be O(m log m) in that case.
- A.filterNot(p => occurrences.contains(p) && isPrime(occurrences(p)))
- }
- val A = Seq(2, 3, 9, 2, 5, 1, 3, 7, 10)
- val B = Seq(2, 1, 3, 4, 3, 10, 6, 6, 1, 7, 10, 10, 10)
- assert(compositeOccurrences(A, B) == Seq(2, 9, 2, 5, 7, 10))
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement