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

Question

Link

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 nth 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.

1. 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).
2. 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)
3. 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)