# [Kotlin] Korean Coding Test - Programmers- Pseudo cantor bit string

KotlinQuestion

In mathematics, a set of cantors is a set of real numbers between 0 and 1, starting at [0, 1] and repeatedly excluding the middle section by dividing each section into three equal parts.

Remain transformed the set of cantors a little bit to create a pseudo cantor bitstream. The pseudo cantor bit string is defined as follows.

- The 0th pseudocantor bit string is "1".
- The n (1 ≤ n)th pseudocantor bit string is created by replacing 1 in the n - 1 pseudocantor bit string with 11011 and 0 with 00000.

I wonder how many 1s are in a particular interval in the `n`

th pseudo cantor bit string that remains.

Complete the solution function to return the number of 1s in the interval given `l`

and `r`

indicating the interval in which you want to know how many `n`

and 1s are.

Restrictions

1 ≤ `n`

≤ 20

1 ≤ `l`

, `r`

≤ 5n

`l`

≤`r`

<`l`

+ 10,000,000`l`

and`r`

are indices in the bit string (1-base) and represent closed intervals [l, r].

Input/Output Example

Input

- n: 2
- l: 4
- r: 17

Output: 8

Solve

Find a Rule

by definition

- 0th pseudo cantor bit string = 1
- n(1 ≤ n)th pseudocantor bit string = value substituted for n-1th pseudocantor bit string

As a result, the first similar cantor bit string becomes 11011 where the 0th similar cantor bit string 1 is replaced.

Looking further, the second and third similar cantor bit strings are as follows

- Second pseudo cantor bit string = value substituted for first pseudo cantor bit string (11011) = 11011 11011 00000 11011 11011 11011

Here we can see three rules.

- If the nth pseudo cantor bit string is f(n), f(1) = 11011. That is,
`f(n) = f(n-1) f(n-1) 0 f(n-1) f(n-1)`

. - The nth bit string may be divided into five equal parts. That is, at f(n), the similar cantor bit string digits are
`5^n`

. (Five decimal) - In f(n), 1 is
`4^n`

. (Quarter Method)

Consider time complexity

According to the rule found above, the number of similar cantor bit string digits is up to 5^20, with 13 digits.

Here, when r is less than l + 10,000,000, r - l < 10,000,000, so to search for a closed interval [l, r], the length is up to 10^7.

Therefore, the time complexity should not exceed O(N).

Divisional conquest

It takes advantage of the fact that the bit string has a certain rule and can be divided into five equal parts.

If `n=2`

, `l=17`

, and `r=25`

- The number of 1s from 17th to 25th bits based on the second bit string = the number of 1s from 25th bit to 1s from 16th bit
- If the second bit string is divided into five zones (0,1,2,3,4), the 17th bit is located in zone 3 and the 25th bit is located in zone 4.

Number of 1s from 2nd bit string to 25th bit = Number of 1s from zone 3 + number of bits from zone 4 to 25th

- Number of 1s to zone 3 = number of 1s to 3 first bit strings = 4^1 * 3 = 12
- Number of bits from zone 4 to 25 = number of bits from 1st bit string to 5th (25-5*4)th bit

Number of 1s to 16th bits = Number of 1s to zone 2 + Number of bits to zone 3 to 16th

- Number of 1s up to zone 2 = number of 1s for 2 first bit strings = 4^1 * 2 = 8
- Number of bits from zone 3 to 16th = number of bits from 1st bit string to 1st bit (16-5*3)

If we implement a function count(n, k) that obtains the number of 1s from the n-th bit string to the k-th bit string, it can be expressed as follows.

`count(n,k) = the number of 1s before zone k + count(n-1,k-(the number of bits before zone k))`

```
zone = zone k(0~4)
count(n, k) =
if (zone == 2) 4^(n-1) * zone
if (zone > 2) 4^(n-1) * (zone-1) + count(n-1, k - (5^(n-1) * zone))
else 4^(n-1) * zone + count(n-1, k - (5^(n-1) * zone))
```

Code

```
import kotlin.math.abs
import kotlin.math.pow
class Solution {
fun solution(n: Int, l: Long, r: Long): Int {
return count(n, r) - count(n, l - 1)
}
private fun count(n: Int, k: Long): Int {
if (n == 0) return 1
val prevBitStringNumber = n - 1
val divisor = 5.0.pow(prevBitStringNumber).toLong() // a number divided into five equal parts
val numberOf1s = 4.0.pow(prevBitStringNumber).toInt() // Number of previous bit string 1
var zone = abs(k / divisor).toInt() // The zone to which the kth belongs (0, 1, 2, 3, 4)
if (k % divisor == 0L) zone -= 1
// a zone with only zero
if (zone == 2) return numberOf1s * zone
// Zones after 0
if (zone > 2) return numberOf1s * (zone - 1) + count(n - 1, k - (divisor * zone))
// Zones prior to zero
return numberOf1s * zone + count(n - 1, k - (divisor * zone))
}
}
```

```
TEST 1 〉 Pass (0.04ms, 62.1MB)
TEST 2 〉 Pass (0.04ms, 62.9MB)
TEST 3 〉 Pass (0.04ms, 62.2MB)
TEST 4 〉 Pass (0.06ms, 62.1MB)
TEST 5 〉 Pass (0.06ms, 59MB)
TEST 6 〉 Pass (0.04ms, 61.3MB)
TEST 7 〉 Pass (0.04ms, 60.8MB)
TEST 8 〉 Pass (0.04ms, 62.4MB)
TEST 9 〉 Pass (0.04ms, 62.5MB)
TEST 10 〉 Pass (0.04ms, 62.7MB)
TEST 11 〉 Pass (0.04ms, 62.4MB)
TEST 12 〉 Pass (0.04ms, 61.4MB)
TEST 13 〉 Pass (0.04ms, 62.1MB)
TEST 14 〉 Pass (0.04ms, 60.7MB)
TEST 15 〉 Pass (0.04ms, 59MB)
```