Problem -

given this sequence of strings

 n  - f(n)
 0  - "" -
 1  - "0"
 2  - "1"
 3  - "00"
 4  - "01"
 5  - "10"
 6  - "11"
 7  - "000"
 8  - "001"
 9  - "010"
 10 - "011"
 11 - "100"
 12 - "101"
 13 - "110"
 14 - "111"
 15 - "0000"

write a function that takes an integer n and produces the nth string in the sequence.

Objervation & Solution -

This problem was given to me as a timed challange. While solving this problem I realized following -

  • it is a good idea to break problem in smaller problem
  • while writing code it helps if we can idntify methods and move them out of core algorithim.
  • and code can be optimized if we keep pateince and work towards it.

When I started working on this problem, my first solution was following.

object Solution extends App {

  def findString(n: Int) : String = {
    val binaryString = n.toBinaryString

    if(n == 0)  {
      ""
    }else if ( !binaryString.contains('0'))  {
       new String(Array.fill[Char](binaryString.size)('0'))
    } else {
      var num = 1
      while (num <= n) {
        num = num*2
      }
      (n-(num/2 -1)).toBinaryString
    }

  }

  for (i <- 0 to 15)
  println(s" $i -> ${findString(i)}")



}

Notice how I screwed up the style guide. Also I feel this solution is not very readable. It is working but it can be more redable. Finally it is not taking care of one aspect of the problem , which is padding required for some number,

Later in the day when I had some more time I came up with a better version of this code in 15 minutes. This version as well may not be the best, but it is for sure better and more readable.

object findthestring {
 // following method is not needed for this problem
 def findNearestAndHigherPowOf2(n: Int) : Int= {
    var found = false
    var num = n
    if ( n == 0 || n == 1 ) 2
    else {
      while (!found) {
        if ( (num & num +1) == 0 ) found = true else num = num +1
      }
      num + 1
    }
  }

  def findNearestAndLowerPowOf2(n: Int) : Int= {
    var found = false
    var num = n
    if ( n == 0 || n == 1) 0
    else {
      while (!found) {
        if ( (num & num -1) == 0 ) found = true else num = num -1
      }
      num
    }
  }

  def findBinaryString(n : Int) : String = {
    if (n == 0) {
      ""
    } else if (!n.toBinaryString.contains('0')) {
      "0" * n.toBinaryString.size
    } else {
      val sizeOfString = (findNearestAndLowerPowOf2(n).toBinaryString).size
      val wothoutPadding = (n - (findNearestAndLowerPowOf2(n) -1)).toBinaryString
      ("0"* (sizeOfString - wothoutPadding.size -1)) + wothoutPadding
    }
  }

  def  main(args: Array[String]) : Unit =  {
    for (i <- 0 to 15)
      println(s" $i -> ${findBinaryString(i)}")
  }
}

This version do have more line of codes, but I think it is worth having them here. They make it more redable. Also I feel the variable names can be lot better. I will fix it later.

You can fin it here.

https://github.com/tuachotu/code-practice/blob/master/findNextString/findthestring.scala

Cheers!!!