CODEWITHSUNDEEP
algorithmscala
user3752500
user3752500

Reputation: 57

Single Number 2 Scala solution

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one. This is what I have now. But I don't know how to break the for loop once I get the single number "b". Any solution in scala please?

for(Array(a,b) <- nums.sorted.sliding(2))
{
  if (a == b){j = j+1}
  else 
   {
      if (j < 3) j =1
      b
   }
}

Upvotes: 1

Views: 122

Answers (2)

Kolmar
Kolmar

Reputation: 14224

Another way is to sum the array by adding digits of two numbers in base 3 modulo 3 (in other words XOR in base 3). The elements that appear 3 times will become zero, so the result of this sum will be the single number.

def findSingleNumber(numbers: Array[Int]) = {
  def add3(a: String, b: String): String = a.zipAll(b, '0', '0').map {
    case (i, j) => ((i.toInt + j.toInt) % 3 + '0').toChar
  }(collection.breakOut)

  val numbersInBase3 = numbers.map(n => Integer.toString(n, 3).reverse) 
  Integer.parseInt(numbersInBase3.fold("0")(add3).reverse, 3)
}

scala> findSingleNumber(Array(10, 20, 30, 100, 20, 100, 10, 10, 20, 100))
res1: Int = 30

Or representing base 3 numbers as digit arrays:

def findSingleNumber(numbers: Array[Int]) = {
  def toBase3(int: Int): Array[Int] =
    Iterator.iterate(int)(_ / 3).takeWhile(_ != 0).map(_ % 3).toArray

  def toBase10(arr: Array[Int]): Int =
    arr.reverseIterator.foldLeft(0)(_ * 3 + _)

  def add3(a: Array[Int], b: Array[Int]): Array[Int] = a.zipAll(b, 0, 0).map {
    case (i, j) => (i + j) % 3
  }

  toBase10(numbers.map(toBase3).fold(Array.empty[Int])(add3))
}

Upvotes: 0

jwvh
jwvh

Reputation: 51271

This will do it.

nums.groupBy(identity).find(_._2.length == 1).get._1

It's a bit unsafe in that it will throw if there is no single-count element. It can be made safer if a default value is returned when no single-count element is found.

nums.groupBy(identity).find(_._2.length == 1).fold(-1)(_._1)

Upvotes: 3

Related Questions