# 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
}
}

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!!!