is it possible to write functional version for below imperative code in scala

Question

I wrote sum code in scala to find the majority element(the element which appears more than n/2 times where 'n' is the no.of elements in an array.I want to know where there is functional / scala native style of version(which includes match cases and transformations like "map/"flatmap" etc..) for the below imperative style of scala code which includes looping. The code which i used in:

object MajorityElement{

 def printMajority(arr:Array[Int]) ={
 var cand:Int=findCandidate(arr);
  if(isMajority(arr,cand))
    println(cand);
  else
    println("No Majority Element");
 }

def isMajority(arr:Array[Int],Cand:Int):Boolean ={
  var count=0;
   for(i <- 0 until arr.length){
    if(arr(i)== Cand)
      count+=1;
    }
 if (count > arr.size/2)
   return true;
 else false
 }

def findCandidate(arr:Array[Int]):Int ={
 val s = arr.size
 var majIndex:Int = 0;
 var count = 1;
  for(i <- 0 until arr.length){

     if(arr(majIndex) == arr(i))
       count+=1;
     else
       count-=1;
     if(count==0)
       {
       majIndex = i;
       count =1
        }
    }
 return arr(majIndex);
  }
}

please let me know, whether it is possible to write/ convert imperative style to functional version in scala(which uses match cases) for any scenario.

Answer 1

Threr is no Native Scala Style, but code can be Functional Style(value oriented)

(No var, No Side-Effect, Pure Function)

object MajorityElement {

  case class Candidate(idx: Int, count: Int)

  def solve(arr: Array[Int]): Option[Int] = {
    val candidate = findCandidate(arr)

    if (isMajority(arr, candidate)) Option(arr(candidate.idx))
    else None
  }

  def isMajority(arr: Array[Int], candidate: Candidate) =
    arr.count(_ == arr(candidate.idx)) > arr.size / 2

  def findCandidate(arr: Array[Int]): Candidate =
    arr.indices.foldLeft(Candidate(0, 1)) { (acc, idx) =>
      val newAcc =
        if (arr(acc.idx) == arr(idx)) acc.copy(count = acc.count + 1)
        else acc.copy(count = acc.count - 1)

      if (newAcc.count == 0) Candidate(idx, 1)
      else newAcc
    }
}

val arr = Array(1, 1, 1, 2, 3, 4, 1)
val ret = MajorityElement.solve(arr)

ret match {
  case Some(n) => println(s"Found Majority Element: $n")
  case None => println("No Majority Element")
}

Answer 2

The transition from imperative thinking to functional thinking takes time and study. One approach is to find code examples here on SO and, with the help of the Standard Library, break it down until you understand what's going on.

Here's a little something to get you started.

def isMajority(arr:Array[Int],cand:Int):Boolean =
  arr.count(_ == cand) > arr.size/2

Answer 3

If you're only interested in the final result (and so you don't need isMajority etc), it's very simple

  def findMajority(xs: List[Int]) = {
    val mostFrequent = xs.groupBy(identity).values.maxBy(_.length)
   if (mostFrequent.length >= xs.length / 2) Some(mostFrequent.head) else None
  } 
  findMajority(List(1, 2, 2, 2, 3, 3, 3, 3, 3, 4))
  //Option[Int] = Some(3)

Group equal elements into lists (the values of the Map returned by GroupBy). Pick the longest list. If its length is more than half the list, then it's a majority, return Some(the head) (any element will do, they're all the same value). Otherwise, return None