find out if a number is a good number in scala

user_10380206 0
Viewed 156

Hi I am new to scala functional programming methodology. I want to input a number to my function and check if it is a good number or not. A number is a good number if its every digit is larger than the sum of digits which are on the right side of that digit.  For example: 9620  is good as (2 > 0, 6 > 2+0, 9 > 6+2+0) steps I am using to solve this is 

1. converting a number to string and reversing it
2. storing all digits of the reversed number as elements of a list
3. applying for loop from  i equals 1 to length of number - 1
4. calculating sum of first i digits as num2
5. extracting ith digit from the list as digit1 which is one digit ahead of the first i numbers for which we calculated sum because list starts from zero.
6. comparing output of 4th and 5th step. if num1 is greater than num2 then we will break the for loop and come out of the loop to print it is not a good number.

please find my code below

val num1 = 9521.toString.reverse
val list1 = num1.map(_.todigit).toList
for (i <- 1 to num1.length - 1) {
  val num2 = num1.take(i).map(_.toDigits) sum
  val digit1 = list1(i)
  if (num2 > digit1) {
    print("number is not a good number")
    break
  }
}

I know this is not the most optimized way to solve this problem. Also I am looking for a way to code this using tail recursion where I pass two numbers and get all the good numbers falling in between those two numbers. Can this be done in more optimized way? Thanks in advance!

scala functional-programming
5 Answers

No String conversions required.

val n = 9620
val isGood = Stream.iterate(n)(_/10)
                   .takeWhile(_>0)
                   .map(_%10)
                   .foldLeft((true,-1)){ case ((bool,sum),digit) =>
                      (bool && digit > sum, sum+digit)
                   }._1
user_49931280

Here is a purely numeric version using a recursive function.

def isGood(n: Int): Boolean = {
  @tailrec
  def loop(n: Int, sum: Int): Boolean =
    (n == 0) || (n%10 > sum && loop(n/10, sum + n%10))

  loop(n/10, n%10)
}

This should compile into an efficient loop.

user_76626700

This is a more functional way. pairs is a list of tuples between a digit and the sum of the following digits. It is easy to create these tuples with drop, take and slice (a combination of drop and take) methods.

Finally I can represent my condition in an expressive way with forall method.

val n = 9620

val str = n.toString

val pairs = for { x <- 1 until str.length } yield (str.slice(x - 1, x).toInt, str.drop(x).map(_.asDigit).sum)

pairs.forall { case (a, b) => a > b }

If you want to be functional and expressive avoid to use break. If you need to check a condition for each element is a good idea to move your problem to collections, so you can use forAll.

This is not the case, but if you want performance (if you don't want to create an entire pairs collection because the condition for the first element is false) you can change your for collection from a Range to Stream.

(1 until str.length).toStream
user_101239810

Using this function:(This will be the efficient way as the function forall will not traverse the entire list of digits. it stops when it finds the false condition immediately ( ie., when v(i)>v.drop(i+1).sum becomes false) while traversing from left to right of the vector v. )

  def isGood(n: Int)= {
   val v1 = n.toString.map(_.asDigit)
   val v = if(v1.last!=0) v1 else v1.dropRight(1)
   (0 to v.size-1).forall(i=>v(i)>v.drop(i+1).sum)
  }

If we want to find good numbers in an interval of integers ranging from n1 to n2 we can use this function:

def goodNums(n1:Int,n2:Int) = (n1 to n2).filter(isGood(_))

In Scala REPL:

scala> isGood(9620)
res51: Boolean = true

scala> isGood(9600)
res52: Boolean = false

scala> isGood(9641)
res53: Boolean = false

scala> isGood(9521)
res54: Boolean = true

scala> goodNums(412,534)
res66: scala.collection.immutable.IndexedSeq[Int] = Vector(420, 421, 430, 510, 520, 521, 530, 531)

scala> goodNums(3412,5334)
res67: scala.collection.immutable.IndexedSeq[Int] = Vector(4210, 5210, 5310)
user_99533160

Functional style tends to prefer monadic type things, such as maps and reduces. To make this look functional and clear, I'd do something like:

def isGood(value: Int) =
  value.toString.reverse.map(digit=>Some(digit.asDigit)).
    reduceLeft[Option[Int]]
    {
      case(sum, Some(digit)) => sum.collectFirst{case sum if sum < digit => sum+digit}
    }.isDefined

Instead of using tail recursion to calculate this for ranges, just generate the range and then filter over it:

def goodInRange(low: Int, high: Int) = (low to high).filter(isGood(_))
user_42683470
Related