package org.geo.scala.fundamentals.examples.tricks

object missingNumber extends App {
  def findMissing(arr: Array[Int]): Int = {
  /** get length of array **/
    val len = arr.length + 1
  /** determine sum of array **/
    val sum = arr.sum
  /** determine sum of complete array **/
    val sumComplete = (len * ( len + 1 ))/2
  /** determine missing number **/
    sumComplete - sum
  }

  def findMissingXor(arr: Array[Int]): Int = {
    /** get the length of the array + 1 **/
    val len = arr.length + 1
    /** perform a fold left operation **/
    var n = (0 /: arr)(_ ^ _)
    /** now exclusiveor with the complete array **/
    val x = (1 to len).foldLeft(n)(_ ^ _)
    x
  }

  /** test it **/
  /** fill an array with 99 entries missing the 8th entry **/
  var arr = new Array[Int](100).indices.map(p => p + 1).filter(_ != 8).toArray[Int]
  /** find the missing value 8 **/
  println("missing number is " + findMissing(arr))

  /** find the missing value 45 **/
  arr = new Array[Int](100).indices.map(p => p + 1).filter(_ != 45).toArray[Int]
  println("missing number is " + findMissing(arr))

  /** try the xor version **/
  println("missing number is " + findMissingXor(arr))

}