brain teaser on missing and duplicated number

xMissing_yDuplicated.scala

import util.Random

// setup:
val size = 1e6.toInt
val sorted = (1 to size).toIndexedSeq
val missing = Random.nextInt(size) + 1
val duplicated = Random.nextInt(size) + 1
val input = Random.shuffle(sorted.filter(_ != missing) :+ duplicated)

// find x and y:
val sortedInput = input.sorted

val map = sortedInput.sliding(2).collect{ 
  case Seq(a, b) if a == b => "dup" -> a
  case Seq(a, b) if b == a + 2 => "missing" -> (a + 1)
}.toMap

printf("missing is %d (expected %d)%n", map.get("missing").getOrElse(-1), missing)
printf("duplicated is %d (expected %d)%n", map.get("dup").getOrElse(-1), duplicated)

// takes less than 6 seconds