Advertisement
Guest User

SMTask1

a guest
Nov 22nd, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 1.42 KB | None | 0 0
  1. object CompositeOccurrences extends App {
  2.   /**
  3.     * Brute force primality test, takes sqrt(x) time with a silent assumption than divisibility checking takes O(1).
  4.     */
  5.   private def isPrime(x: Int): Boolean = {
  6.     assert(x >= 0)
  7.     if (x < 2) return false
  8.     else if (x == 2) return true
  9.     val i = 2
  10.     while (i*i <= x) {
  11.       if (x % i == 0) return false
  12.     }
  13.     true
  14.   }
  15.  
  16.   /**
  17.     * Returns all elements from sequence A (maintaining the order) except those, that are present in sequence B p times,
  18.     * where p is a prime number.
  19.     */
  20.   def compositeOccurrences(A: Seq[Int], B: Seq[Int]): Seq[Int] = {
  21.     // creating map of B elements takes O(n log n) time (groupBy), where is n is B size.
  22.     val occurrences = B.groupBy(x => x).mapValues(_.length)
  23.  
  24.     // For every element in A (of size O(m)) we do primality test on number of occurrences in B. They are potentially unlimited,
  25.     // 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,
  26.     // then filtering A takes approximately sqrt(s1) + ... + sqrt(s_m) <= m. So the overall complexity would be O(m log m) in that case.
  27.     A.filterNot(p => occurrences.contains(p) && isPrime(occurrences(p)))
  28.   }
  29.  
  30.   val A = Seq(2, 3, 9, 2, 5, 1, 3, 7, 10)
  31.   val B = Seq(2, 1, 3, 4, 3, 10, 6, 6, 1, 7, 10, 10, 10)
  32.  
  33.   assert(compositeOccurrences(A, B) == Seq(2, 9, 2, 5, 7, 10))
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement